Centered coloring

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 $q$ -centered coloring, provides a way of covering graphs with a small number of subgraphs of treedepth at most $q$ , and can be used in algorithms for subgraph isomorphism and related problems. The number of colors needed for a $q$ -centered coloring is bounded as a function of $q$ in the graphs of bounded expansion.

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 $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 $q$ colors, or it has at least one vertex whose color is unique.^[2] For $q=2$ this is an ordinary graph coloring: every edge, and therefore every larger connected subgraph, must have at least two colors.^[3] For $q=3$ a $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 $q>n$ , where $n$ is the number of vertices in the graph, it is impossible to have $q$ colors, and a $q$ -centered coloring is the same thing as a centered coloring without the parameter. More strongly, whenever $q$ is at least equal to the treedepth $t$ of a given graph, the number of colors in a $q$ -centered coloring is also at least equal to $t$ .^[4]

Equivalence with treedepth

The minimum number of colors in a centered coloring of a given graph $G$ equals its tree-depth, the minimum height of a rooted forest $F$ on the same vertex set as $G$ such that every edge in $G$ connects an ancestor–descendant pair in $F$ . In one direction, if $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 $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 $G$ , one can obtain a forest $F$ with the desired properties, by choosing a tree root with a unique color in each component of $G$ , with the children of each root constructed recursively from the connected subgraphs obtained by removing the root from $G$ .^[5]

Algorithmic application

In a $q$ -centered coloring, every subset of $k$ colors where $k<q$ induces a subgraph on which the coloring is a centered coloring. This induced subgraph therefore has tree-depth at most $k$ .^[6] By choosing all subsets of a given number of colors, any graph with a $q$ -centered coloring can be covered by graphs of bounded tree-depth. In particular, if one wishes to search for copies of a graph $H$ with $h$ vertices as subgraphs of a larger graph $G$ (the subgraph isomorphism problem), and $G$ has an $(h+1)$ -centered coloring with $k$ colors, then any copy of $H$ can use at most $h$ of the colors. One can find all copies of $H$ in the subgraphs of $G$ induced by all $h$ -tuples of colors. This idea reduces the subgraph isomorphism problem to $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 $G$ models any first-order formula in the logic of graphs that uses only $h$ variables.^[7]

For this method to be efficient, it is important that the number of colors in a $q$ -centered coloring be small. For graphs of bounded expansion, this number is bounded by a polynomial of $q$ whose (large) exponent depends on the family.^[8] More generally, for graphs in a nowhere-dense family of graphs, this number is $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 $O(q)$ , for planar graphs it is $O(q^{3}\log q)$ , and for graphs with a forbidden topological minor it is polynomial in $q$ .^[10]

Notes

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

Centered coloring

Equivalence with treedepth

Algorithmic application

Notes

References

Related Articles