Critical graph

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.

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 ${\displaystyle k}$-critical graph is a critical graph with chromatic number ${\displaystyle k}$. A graph ${\displaystyle G}$ with chromatic number ${\displaystyle k}$ is ${\displaystyle 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 ${\displaystyle k}$-critical graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices and ${\displaystyle m}$ edges:

• ${\displaystyle G}$ has only one component.
• ${\displaystyle G}$ is finite (this is the De Bruijn–Erdős theorem). ^[1]
• The minimum degree ${\displaystyle \delta (G)}$ obeys the inequality ${\displaystyle \delta (G)\geq k-1}$. That is, every vertex is adjacent to at least ${\displaystyle k-1}$ others. More strongly, ${\displaystyle G}$ is ${\displaystyle (k-1)}$-edge-connected. ^[2]
• If ${\displaystyle G}$ is a regular graph with degree ${\displaystyle k-1}$, meaning every vertex is adjacent to exactly ${\displaystyle k-1}$ others, then ${\displaystyle G}$ is either the complete graph ${\displaystyle K_{k}}$ with ${\displaystyle n=k}$ vertices, or an odd-length cycle graph. This is Brooks' theorem. ^[3]
• ${\displaystyle 2m\geq (k-1)n+k-3}$. ^[4]
• ${\displaystyle 2m\geq (k-1)n+\lfloor (k-3)/(k^{2}-3)\rfloor n}$. ^[5]
• Either ${\displaystyle 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 ${\displaystyle G}$ has at least ${\displaystyle 2k-1}$ vertices. ^[6] More strongly, either ${\displaystyle G}$ has a decomposition of this type, or for every vertex ${\displaystyle v}$ of ${\displaystyle G}$ there is a ${\displaystyle k}$-coloring in which ${\displaystyle v}$ is the only vertex of its color and every other color class has at least two vertices. ^[7]

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

As Hajós (1961) showed, every ${\displaystyle k}$-critical graph may be formed from a complete graph ${\displaystyle 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 ${\displaystyle k}$ colors in any proper coloring. ^[8]

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 ${\displaystyle K_{k}}$ is the only double-critical ${\displaystyle k}$-chromatic graph. ^[9]

See also

• Factor-critical graph

References

1. 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, CiteSeerX   10.1.1.210.6623 , doi:10.1016/S1385-7258(51)50053-7 . (Indag. Math. 13.)
2. Lovász, László (1992), "Solution to Exercise 9.21", Combinatorial Problems and Exercises (2nd ed.), North-Holland, ISBN   978-0-8218-6947-5
3. 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
4. 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
5. Gallai, T. (1963), "Kritische Graphen I", Publ. Math. Inst. Hungar. Acad. Sci., 8: 165–192
6. Gallai, T. (1963), "Kritische Graphen II", Publ. Math. Inst. Hungar. Acad. Sci., 8: 373–395
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
8. 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
9. Erdős, Paul (1967), "Problem 2", In Theory of Graphs, Proc. Colloq., Tihany, p. 361

Further reading

• Jensen, T. R.; Toft, B. (1995), Graph coloring problems, New York: Wiley-Interscience, ISBN   0-471-02865-7
• Stiebitz, Michael; Tuza, Zsolt; Voigt, Margit (6 August 2009), "On list critical graphs", Discrete Mathematics, 309 (15), Elsevier: 4931–4941, doi:10.1016/j.disc.2008.05.021