Improved Bounds for Centered Colorings

Divide-and-conquer algorithm design is a programming technique based on decomposing an input instance into smaller instances, which are then solved and their solutions are combined to form a solution of the original instance. Tree-depth is an important graph parameter that measures the complexity of one such way of decomposing graphs: the tree-depth of a single vertex graph is one and the tree-depth of a connected graph $G$ is the smallest $d$ such that there exists a vertex $v$ such that each component of $G\setminus v$ has tree-depth at most $d-1$. Equivalently, the tree-depth of a graph $G$ is the smallest $k$ for which there exists a $k$-vertex coloring such that every connected subgraph of $G$ has a vertex colored with a unique color; a vertex-coloring with this property is called a centered coloring.

Many sparse graphs, e.g., planar graphs, do not have small tree-depth in general but admit multicovers by graphs of small tree-depth, which can be used to design efficient algorithms using dynamic programming techniques. This led to the definition of graph classes with bounded expansion, which has quickly become an important notion both in structural and algorithmic graph theory: a class of graphs has bounded expansion if for every $p$, there exists $k$ such that every graph in the class has a $k$-vertex-coloring such that the restriction of the coloring to any $p'\le p$ color classes is a centered coloring, in particular, the tree-depth of the subgraph induced by the $p'$ color classes is at most $p'$. A $k$-vertex-coloring with this property is called a $p$-centered coloring.

The authors present polynomial upper bounds on the number of colors needed in a $p$-centered coloring for several important classes of sparse graphs and also complement these results with non-trivial lower bounds. In particular, they show that every planar graph has a $p$-centered coloring using at most $O(p^3\log p)$ colors (while at least $\Omega(p^2\log p)$ colors are needed in general), every class of graphs with bounded degree admits $p$-centered colorings with at most $O(p)$ colors and every class of graphs avoiding a topological minor with at most a polynomial number of colors; moreover, there exist polynomial-time algorithms to construct such $p$-centered colorings.