Centered coloring

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 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. ==Notes==