Centered coloring

Summary

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.