---
tag: EFMH402625
kind: concept
name: Centered coloring
sources:
  - wikipedia: en:81758007@r1326299770
    locator: Centered coloring
    note: adopted
    mention: wikipedia://en/81758007
    sections: [Summary]
same_as:
  wikidata: Q137441810
  wikipedia: Centered coloring
inventory: [EKZW3JBBNJ]
---

## Summary

In graph theory, a **centered coloring** is a type of [[graph coloring|0NCPXH194Y]] 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.