{
  "id": "enwiki-001377270557",
  "slug": "centered-coloring",
  "title": "Centered coloring",
  "qid": "",
  "lead": "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.",
  "body": "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 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 function of q . 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== ==References==",
  "categories": [
    "23603337",
    "26220375",
    "29176365",
    "29264962",
    "65358969"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1377270557",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1790606851.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001377270557",
    "type": "webpage",
    "title": "Centered coloring",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/centered-coloring",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001377270557",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1377270557",
    "note": "Immutable snapshot enwiki-001377270557"
  }
}