Critical graph

In graph theory, a critical graph is a graph G in which every vertex or edge is a critical element, that is, if its deletion decreases the chromatic number of G. Such a decrease cannot be by more than 1.

Not to be confused with the Critical path method, a concept in project management.

On the left-top a vertex critical graph with chromatic number 6; next all the N-1 subgraphs with chromatic number 5.

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 of de Bruijn & Erdős 1951).
• δ(G) ≥ k − 1, that is, every vertex is adjacent to at least k − 1 others. More strongly, G is (k − 1)-edge-connected. See Lovász (1992)
• If G is (k − 1)-regular, meaning every vertex is adjacent to exactly k − 1 others, then G is either K_k or an odd cycle . This is Brooks' theorem; see Brooks & Tutte (1941)).
• 2 m ≥ (k − 1) n + k − 3 (Dirac 1957).
• 2 m ≥ (k − 1) n + [(k − 3)/(k² − 3)] n (Gallai 1963a).
• 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 2k - 1 vertices (Gallai 1963b). 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 (Stehlík 2003).

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.

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. One open problem is to determine whether K_k is the only double-critical k-chromatic graph.[1]

See also

• Factor-critical graph

References

1. Erdős 1967.

Sources

• Brooks, R. L.; Tutte, W. T. (1941), "On colouring the nodes of a network", Proceedings of the Cambridge Philosophical Society, 37 (02): 194–197, doi:10.1017/S030500410002168X
• 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. (Indag. Math. 13.)
• 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
• Erdős, Paul (1967), "Problem 2", In Theory of Graphs, Proc. Colloq., Tihany, p. 361CS1 maint: ref=harv (link)
• Gallai, T. (1963a), "Kritische Graphen I", Publ. Math. Inst. Hungar. Acad. Sci., 8: 165–192
• Gallai, T. (1963b), "Kritische Graphen II", Publ. Math. Inst. Hungar. Acad. Sci., 8: 373–395
• 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.
• Jensen, T. R.; Toft, B. (1995), Graph coloring problems, New York: Wiley-Interscience, ISBN 0-471-02865-7
• 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.
• Lovász, László (1992), "Solution to Exercise 9.21", Combinatorial Problems and Exercises (Second Edition), North-Holland
• Stiebitz, Michael; Tuza, Zsolt; Voigt, Margit (6 August 2009), "On list critical graphs", Discrete Mathematics, Elsevier, 309 (15): 4931–4941, doi:10.1016/j.disc.2008.05.021