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 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 Kk 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)/(k2 − 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 Kk 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 Kk is the only double-critical k-chromatic graph.[1]

See also

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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.