Centered coloring

A centered coloring of a graph. Each connected subgraph has a color used by exactly one vertex. The number of colors, four, equals the tree-depth of the graph.

In graph theory, a centered coloring is a type of graph coloring related to treedepth. The minimum number of colors in a centered coloring of a graph equals the graph's treedepth. A parameterized variant, a ${\displaystyle q}$-centered coloring, provides a way of covering graphs with a small number of subgraphs of treedepth at most ${\displaystyle q}$, and can be used in algorithms for subgraph isomorphism and related problems. The number of colors needed for a ${\displaystyle q}$-centered coloring is bounded as a function of ${\displaystyle q}$ in the graphs of bounded expansion.

Definition

A centered coloring is a graph coloring, an assignment of colors to the vertices of a given graph, with the following property: every connected subgraph (or equivalently every connected induced subgraph) has at least one vertex whose color is unique: no other vertex in the same subgraph has the same color. ^[1]

A ${\displaystyle q}$-centered coloring is a centered coloring with the weaker property that every connected subgraph (or equivalently every connected induced subgraph) either has at least ${\displaystyle q}$ colors, or it has at least one vertex whose color is unique. ^[2] For ${\displaystyle q=2}$ this is an ordinary graph coloring: every edge, and therefore every larger connected subgraph, must have at least two colors. ^[3] For ${\displaystyle q=3}$ a ${\displaystyle q}$-centered coloring is the same thing as a star coloring: every subgraph with only two colors must be a disjoint union of stars, centered at the uniquely colored vertices of each component. For ${\displaystyle q>n}$, where ${\displaystyle n}$ is the number of vertices in the graph, it is impossible to have ${\displaystyle q}$ colors, and a ${\displaystyle q}$-centered coloring is the same thing as a centered coloring without the parameter. More strongly, whenever ${\displaystyle q}$ is at least equal to the treedepth ${\displaystyle t}$ of a given graph, the number of colors in a ${\displaystyle q}$-centered coloring is also at least equal to ${\displaystyle t}$. ^[4]

Equivalence with treedepth

The minimum number of colors in a centered coloring of a given graph ${\displaystyle G}$ equals its tree-depth, the minimum height of a rooted forest ${\displaystyle F}$ on the same vertex set as ${\displaystyle G}$ such that every edge in ${\displaystyle G}$ connects an ancestor–descendant pair in ${\displaystyle F}$. In one direction, if ${\displaystyle F}$ is a forest with this property, a centered coloring with a number of colors equal to its height can be obtained by grouping the vertices of ${\displaystyle F}$ by distance from the roots of their trees and using one color for each group. In the other direction, from a centered coloring of ${\displaystyle G}$, one can obtain a forest ${\displaystyle F}$ with the desired properties, by choosing a tree root with a unique color in each component of ${\displaystyle G}$, with the children of each root constructed recursively from the connected subgraphs obtained by removing the root from ${\displaystyle G}$. ^[5]

Algorithmic application

In a ${\displaystyle q}$-centered coloring, every subset of ${\displaystyle k}$ colors where ${\displaystyle k<q}$ induces a subgraph on which the coloring is a centered coloring. This induced subgraph therefore has tree-depth at most ${\displaystyle k}$. ^[6] By choosing all subsets of a given number of colors, any graph with a ${\displaystyle q}$-centered coloring can be covered by graphs of bounded tree-depth. In particular, if one wishes to search for copies of a graph ${\displaystyle H}$ with ${\displaystyle h}$ vertices as subgraphs of a larger graph ${\displaystyle G}$ (the subgraph isomorphism problem), and ${\displaystyle G}$ has an ${\displaystyle (h+1)}$-centered coloring with ${\displaystyle k}$ colors, then any copy of ${\displaystyle H}$ can use at most ${\displaystyle h}$ of the colors. One can find all copies of ${\displaystyle H}$ in the subgraphs of ${\displaystyle G}$ induced by all ${\displaystyle h}$-tuples of colors. This idea reduces the subgraph isomorphism problem to ${\displaystyle O(k^{h})}$ subproblems, each of which can be solved quickly because of its low tree-depth. The same idea applies also to checking whether ${\displaystyle G}$ models any first-order formula in the logic of graphs that uses only ${\displaystyle h}$ variables. ^[7]

For this method to be efficient, it is important that the number of colors in a ${\displaystyle q}$-centered coloring be small. For graphs of bounded expansion, this number is bounded by a polynomial of ${\displaystyle q}$ whose (large) exponent depends on the family. ^[8] More generally, for graphs in a nowhere-dense family of graphs, this number is ${\displaystyle o(|V(G)|).}$ However, for graphs classes that are somewhere dense (that is, not nowhere-dense), no such bound is possible. ^[9] For graphs of bounded degree, the number of colors is ${\displaystyle O(q)}$, for planar graphs it is ${\displaystyle O(q^{3}\log q)}$, and for graphs with a forbidden topological minor it is polynomial in ${\displaystyle q}$. ^[10]

Notes

1. Nešetřil & Ossona de Mendez (2012), p. 125, Definition 6.2.
2. Nešetřil & Ossona de Mendez (2012), p. 154, Definition 7.3.
3. Nešetřil & Ossona de Mendez (2012 , p. 150). The equivalence between the numbers denoted here as ${\displaystyle \chi _{p}}$ and the minimum number of colors in a ${\displaystyle (p+1)-centered}$ coloring is Nešetřil & Ossona de Mendez (2012 , p. 154, Corollary 7.1).
4. Nešetřil & Ossona de Mendez (2012), p. 154, Lemma 7.1.
5. Nešetřil & Ossona de Mendez (2012), p. 127, Proposition 6.6.
6. Nešetřil & Ossona de Mendez (2012), p. 154, Corollary 7.1.
7. Nešetřil & Ossona de Mendez (2012), pp. 400–402, Section 18.3: The subgraph isomorphism problem and Boolean queries.
8. Nešetřil & Ossona de Mendez (2012), p. 166, Theorem 7.8.
9. Nešetřil & Ossona de Mendez (2012), p. 168, Theorem 7.9.
10. Dębski et al. (2021).

References

• Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021), "Improved bounds for centered colorings", Advances in Combinatorics 8, doi:10.19086/aic.27351, MR   4309118
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, doi:10.1007/978-3-642-27875-4, ISBN   978-3-642-27874-7, MR   2920058