Jump to content

Critical graph

From Wikipedia, the free encyclopedia
(Redirected from Double critical graph)
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. The decrease in the number of colors cannot be by more than one.

Variations

[edit]

A -critical graph is a critical graph with chromatic number . A graph with chromatic number is -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 -critical graph with vertices and edges:

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

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

As Hajós (1961) showed, every -critical graph may be formed from a complete graph by combining the Hajós construction with an operation that identifies two non-adjacent vertices. The graphs formed in this way always require 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 is the only double-critical -chromatic graph.[9]

See also

[edit]

References

[edit]
  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

[edit]