Centered coloring

Short description: Graph coloring related to treedepth

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 $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.

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.

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. For $q=2$ this is an ordinary graph coloring: every edge, and therefore every larger connected subgraph, must have at least two colors. 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$.

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$.

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$. 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.

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. 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. 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$.

References

• Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021), "Improved bounds for centered colorings", Advances in Combinatorics, doi:10.19086/aic.27351 
• Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, 28, Springer, 2012, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7