Critical graph

In graph theory, a critical graph is an undirected graph all of whose proper subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. Each time a single edge or vertex (along with its incident edges) is removed from a critical graph, the decrease in the number of colors needed to color that graph cannot be by more than one.

Variations

A $k$ -critical graph is a critical graph with chromatic number $k$ . A graph $G$ with chromatic number $k$ is $k$ -vertex-critical if each of its vertices is a critical element. Critical graphs are the minimal members in terms of chromatic number, which is a very important measure in graph theory.

Some properties of a $k$ -critical graph $G$ with $n$ vertices and $m$ edges:

$G$ has only one component.
$G$ is finite (this is the De Bruijn–Erdős theorem).
The minimum degree $δ (G)$ obeys the inequality $δ (G) \geq k - 1$ . That is, every vertex is adjacent to at least $k - 1$ others. More strongly, $G$ is $(k - 1)$ -edge-connected.
If $G$ is a regular graph with degree $k - 1$ , meaning every vertex is adjacent to exactly $k - 1$ others, then $G$ is either the complete graph $K_{k}$ with $n = k$ vertices, or an odd-length cycle graph. This is Brooks' theorem.
$2 m \geq (k - 1) n + k - 3$ .
$2 m \geq (k - 1) n + (k - 3) / (k^{2} - 3) n$ .
Either $G$ may be decomposed into two smaller critical graphs, with an edge between every pair of vertices that includes one vertex from each of the two subgraphs, or $G$ has at least $2 k - 1$ vertices. More strongly, either $G$ has a decomposition of this type, or for every vertex $v$ of $G$ there is a $k$ -coloring in which $v$ is the only vertex of its color and every other color class has at least two vertices.

Graph $G$ is vertex-critical if and only if for every vertex $v$ , there is an optimal proper coloring in which $v$ is a singleton color class.

Dirac's critical-graph conjecture asks whether, for every integer k ≥ 4, there is a k-vertex-critical graph with no critical edge. Tommy R. Jensen established this for every k ≥ 5 in 2002; a 2026 working paper by Alex Chan completes the conjecture by offering a construction for the remaining case k = 4.

As Hajós (1961) showed, every $k$ -critical graph may be formed from a complete graph $K_{k}$ by combining the Hajós construction with an operation that identifies two non-adjacent vertices. The graphs formed in this way always require $k$ colors in any proper coloring.

A double-critical graph is a connected graph in which the deletion of any pair of adjacent vertices decreases the chromatic number by two. It is an open problem to determine whether $K_{k}$ is the only double-critical $k$ -chromatic graph (as claimed by the Erdös-Lovász double critical conjecture).

References

↑ de Bruijn, N. G.; Erdős, P. (1951), "A colour problem for infinite graphs and a problem in the theory of relations", Nederl. Akad. Wetensch. Proc. Ser. A, 54: 371–373, doi:10.1016/S1385-7258(51)50053-7. (Indag. Math. 13.)
↑ Lovász, László (1992), "Solution to Exercise 9.21", Combinatorial Problems and Exercises (2nd ed.), North-Holland, ISBN 978-0-8218-6947-5
↑ Brooks, R. L. (1941), "On colouring the nodes of a network", Proceedings of the Cambridge Philosophical Society, 37 (2): 194–197, Bibcode:1941PCPS...37..194B, doi:10.1017/S030500410002168X, S2CID 209835194
↑ Dirac, G. A. (1957), "A theorem of R. L. Brooks and a conjecture of H. Hadwiger", Proceedings of the London Mathematical Society, 7 (1): 161–195, doi:10.1112/plms/s3-7.1.161
↑ Gallai, T. (1963), "Kritische Graphen I", Publ. Math. Inst. Hungar. Acad. Sci., 8: 165–192
↑ Gallai, T. (1963), "Kritische Graphen II", Publ. Math. Inst. Hungar. Acad. Sci., 8: 373–395
↑ Stehlík, Matěj (2003), "Critical graphs with connected complements", Journal of Combinatorial Theory, Series B, 89 (2): 189–194, doi:10.1016/S0095-8956(03)00069-8, MR 2017723
↑ Jensen, Tommy R. (2002). "Dense critical and vertex-critical graphs". Discrete Mathematics. 258 (1–3): 63–84. doi:10.1016/S0012-365X(02)00262-5.
↑ Chan, Alex (2026). Buying a Station or Relaxing a Constraint? Spectrum Repacking and Dirac's Conjecture (Report). National Bureau of Economic Research. doi:10.3386/w35757.
↑ Hajós, G. (1961), "Über eine Konstruktion nicht $n$ -färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10: 116–117
↑ Erdős, Paul (1967), "Problem 2", In Theory of Graphs, Proc. Colloq., Tihany, p. 361

Critical graph

Variations

See also

References

Further reading