User:2bitdinosaur/sandbox

In graph theory, p-centered colorings are a generalization of proper vertex colorings and form one of the families of parameters that mathematically formalize the notion of graph sparsity.^[1] The concept was originally introduced as a local approximation of centered colorings. One of the main reasons for studying graph sparsity stems from the desire to develop efficient algorithms for problems which are computationally hard when no structural restrictions are posed on the underlying graph. This, in turn, has naturally lead to the introduction of the class of graphs of bounded expansion and the class of graphs which are nowhere dense. These properties are weak enough to allow us to capture a wide assortment of graphs, such as the class of graphs excluding a fixed minor or graphs of bounded book-thickness, yet rich enough to capture enough structure to allow for the implementation of efficient algorithms. For instance, Dvořák, Kráľ and Thomas have devised an FPT algorithm for testing first-order definable properties in graph classes of bounded expansion.^[2]

Definition

A vertex coloring φ of a graph G is p-centered if for every connected subgraph H of G, either:

φ uses more than p colors on G or
there is a color that appears exactly once in H

For p=1, the definition of 1-centered colorings coincides with the one for proper vertex colorings, as each edge induces an isomorphic copy of $\mathrm {K} _{2}$ , the complete graph on 2 vertices, which must receive 2 distinct colors under φ.

The 2-centered colorings of a graph G are exactly its star colorings.

An arbitrary graph G can always be colored in a p-centered manner for any $p\geq 1$ simply by assigning each vertex $v\in G$ a unique color.

The p-chromatic number of G is by definition the smallest number of colors necessary for a p-centered coloring of G and is denoted by $\chi _{p}(G)$ .

A p-centered coloring of G is also a treedepth-p coloring. This fact underpins the importance of p-centered colorings, as low treedepth colorings are a central tool in designing parameterized algorithms in classes of bounded expansion. The running time of algorithms based on p-centered colorings clearly depends on the number of colors used. Therefore, designing efficient coloring procedures with as few colors as possible is desirable.^[1]

Relation to bounded expansion

p-centered colorings play an important role in structural graph theory, as they allow for an equivalent description for when a graph class is of bounded expansion, a concept originally defined in terms of maximum densities of shallow minors.^[3] Nešetřil and Ossona de Mendez, who first introduced the notion of bounded expansion, have proven that a graph class C is of bounded expansion if and only if for every integer $p\geq 1$ and every graph G in C there exists a function $f:\mathbb {N} \rightarrow \mathbb {N}$ such that $\chi _{p}(G)\leq f(p)$ . Thus, the function f offers a uniform bound on the p-chromatic number over the entire class G.

Properties

Upper bounds on the p-centered chromatic number

If G is an arbitrary graph, then $\mid V(G)\mid$ is a trivial upper bound on $\chi _{p}(G)$ . However, restricting our attention to some special proper subclasses of the class of all graphs, we may obtain a uniform upper bound on $\chi _{p}(G)$ which depends only on the parameter p and the class C, but not on the graph G itself. The following bounds are due to Dębski, Felsner, Micek, and Schröder^[1]:

Planar graphs admit p-centered colorings with ${\mathcal {O}}(p^{3}\log p)$ colors.
Graphs with Euler genus g admit p-centered colorings with ${\mathcal {O}}(gp+p^{3}\log p)$ colors.
Graphs with bounded degree admit p-centered colorings with ${\mathcal {O}}(p)$ colors. Specifically, if G has maximum degree at most $\Delta$ , then $\chi _{p}(G)\leq \lceil 2^{10}\cdot \Delta ^{2-1/p}\cdot p\rceil$
For every graph H there is a polynomial f such that the graphs excluding H as a topological minor admit p-centered colorings with at most $f(p)$ colors.
Outerplanar graphs admit p-centered colorings with ${\mathcal {O}}(p\log p)$ colors.
Planar graphs of treewidth at most 3 admit p-centered colorings with ${\mathcal {O}}(p^{2}\log p)$ colors.
Graphs of simple treewidth at most k admit p-centered colorings with ${\mathcal {O}}(p^{k-1}\log p)$ colors.

All of the above mentioned bounds are also supported by polynomial time algorithms that may compute the coloring.

Moreover, Pilipczuk and Siebert have shown that for every $p\geq 1$ , $t\geq 1$ , every graph G of treewidth at most t has $\chi _{p}(G)\leq {\binom {p+t}{t}}$ .^[4]

Lower bounds on the p-centered chromatic number

Since a p-centered coloring of a graph G is also a proper coloring, we always have $\chi (G)\leq \chi _{p}(G)$ . Similarly to the results above, in some situations we may also bound the p-chromatic number from below, more specifically:

There is a family of outerplanar graphs that require $\Omega (p\log p)$ colors in any p-centered coloring.
There is a family of planar graphs of treewidth 3 that require $\Omega (p^{2}\log p)$ colors in any p-centered coloring.
There is a family of graphs of simple treewidth k that require $\Omega (p^{k-1}\log p)$ colors in any p-centered coloring.
For any $p\geq 1$ and $t\geq 1$ there is a graph of treewidth at most t with $\chi _{p}(G)\geq {\binom {p+t}{t}}$ . This implies that the upper bound proposed by Pilipczuk and Siebert is indeed sharp.