Critical graph

At the top left is a vertex critical graph with chromatic number 6. The remaining N-1 subgraphs have chromatic number 5.

A critical graph is a graph in which the removal of any vertex or edge reduces the chromatic number of the graph.

Content

1 Related Definitions
2 Properties
3 Variations and generalizations
4 See also
5 notes
6 Literature

Related Definitions

$k$ ${\ displaystyle k}$ A critical graph is a critical graph with chromatic number k .
A graph G with chromatic number k is vertex k -critical if each of its vertices is a critical element ^[1] .

Properties

Let G be a k- critical graph with n vertices and m edges. Then:
- G has only one component .
- G is finite ( de Bruyne – Erdös theorem ^[2] ).
- δ ( G ) ≥ k - 1, i.e., any vertex is adjacent to at least k - 1 other vertices. More strictly, G is edge ( k - 1) -connected ^[3] .
- If the graph G is ( k - 1) -regular (each vertex is adjacent exactly k - 1 to the other), then the graph G is either a complete graph K _k or an odd cycle . (This is Brooks theorem ^[4] ).
- 2 m ≥ ( k - 1) n + k - 3 ^[5] .
- 2 m ≥ ( k - 1) n + [( k - 3) / ( k ² - 3)] n ^[6] .
- Either G can be divided into two smaller critical graphs with an edge between each pair of vertices, where two vertices are taken from different parts, or the graph G has at least 2 k - 1 vertices ^[7] . More strictly, either G has decompositions of this type, or for each vertex v of the graph G there is a k- coloring in which v is the only vertex with its own color, and all other color classes have at least two vertices ^[8] .

A graph G is vertex critical if and only if for any vertex v there exists an optimal suitable coloring in which the vertex v alone represents the color class.

1-critical graphs do not exist.
The only 2-critical graph is K ₃ .
All 3-critical graphs are exhausted by simple cycles of odd length ^[9] .

As Hajos ^[10] showed, any k- critical graph can be formed from a complete graph K _k by combining the Hayosh construction with the operation of identifying two non-adjacent vertices. A graph formed in this way always requires k colors in any correct coloring.

4-critical, but not edge-critical graph, since

\chi (G-x)=4

{\ displaystyle \ chi (Gx) = 4}

Although each edge-critical graph is necessarily critical, the converse is not true. For example, the graph shown on the right is 4-critical, but not edge-critical ^[11] .

Variations and generalizations

A doubly critical graph is a connected graph in which removing any pair of adjacent vertices reduces the chromatic number by two. One of the unsolved problems is whether K _{k is the} only doubly critical k -chromatic graph ^[12] .

Notes

↑ It should be noted that a critical graph is not always understood to mean a critical k -chromatic graph. In a Wizing article, a critical graph of dimension k means a graph whose dimension of any eigenpart is less than k. In this case, the dimension of the graph is understood as the minimum dimension of the metric space into which the graph can be embedded so that all adjacent vertices are at a distance of 1. ( Vizing 1968 )
↑ de Bruijn, Erdős, 1951 .
↑ Lovász, 1992 .
↑ Brooks, Tutte, 1941 .
↑ Dirac, 1957 .
↑ Gallai, 1963a .
↑ Gallai, 1963b .
↑ Stehlík, 2003 .
↑ Harari, 2003 , p. 167.
↑ Hajós, 1961 .
↑ Harari, 2003 , p. 168-169.
↑ Erdős, 1966 .

Literature

RL Brooks, WT Tutte. On coloring the nodes of a network // Proceedings of the Cambridge Philosophical Society. - 1941.- T. 37 , no. 02 . - S. 194–197 . - DOI : 10.1017 / S030500410002168X .
NG de Bruijn , P. Erdős . A color problem for infinite graphs and a problem in the theory of relations // Nederl. Akad. Wetensch. Proc. Ser. A. - 1951. - T. 54 . - S. 371–373 . . ( Indag. Math. 13. )
GA Dirac. A theorem of RL Brooks and a conjecture of H. Hadwiger // Proceedings of the London Mathematical Society. - 1957. - T. 7 , no. 1 . - S. 161–195 . - DOI : 10.1112 / plms / s3-7.1.161 .
T. Gallai. Kritische Graphen I // Publ. Math. Inst. Hungar. Acad. Sci .. - 1963a. - T. 8 . - S. 165–192 .
T. Gallai. Kritische Graphen II // Publ. Math. Inst. Hungar. Acad. Sci .. - 1963b. - T. 8 . - S. 373–395 . .
G. Hajós . Über eine Konstruktion nicht n -färbbarer Graphen // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. - 1961.- T. 10 . - S. 116–117 .
TR Jensen, B. Toft. Graph coloring problems. - New York: Wiley-Interscience, 1995 .-- ISBN 0-471-02865-7 .
Matěj Stehlík. Critical graphs with connected complements // Journal of Combinatorial Theory . - 2003. - T. 89 , no. 2 . - S. 189–194 . - DOI : 10.1016 / S0095-8956 (03) 00069-8 .
László Lovász . Combinatorial Problems and Exercises (Second Edition). - North-Holland, 1992.
Paul Erdős . In Theory of Graphs. - Proc. Colloq., Tihany, 1966 .-- S. 361.
V. G. Vizing. Some unsolved problems in graph theory // Advances in Mathematical Sciences. - 1968. - T. XXIII , issue. 6 (144) . - S. 117–134 .
F. Harari. Graph theory. - 2nd. - M .: URSS editorial, 2003. - ISBN 5-354-00301-6 , LBC 22.144, 22.18, 22.19.

[1] It should be noted that a critical graph is not always understood to mean a critical k -chromatic graph. In a Wizing article, a critical graph of dimension k means a graph whose dimension of any eigenpart is less than k. In this case, the dimension of the graph is understood as the minimum dimension of the metric space into which the graph can be embedded so that all adjacent vertices are at a distance of 1. ( Vizing 1968 )

[_d10824dc852fe0b0-2] Bruijn, Erdős, 1951 .

[_b2e5e2e96b8ea240-3] Lovász, 1992 .

[_1161b51af6b3deaa-4] Brooks, Tutte, 1941 .

[_0ec5e10f91cbf4c6-5] Dirac, 1957 .

[_d40c18d8069456d5-6] Gallai, 1963a .

[_074575439765b882-7] Gallai, 1963b .

[_b8e09649987cf18f-8] Stehlík, 2003 .

[_32f94cf53d36d7c5-9] Harari, 2003 , p. 167.

[_853566e85d4e6abe-10] Hajós, 1961 .

[_c52d4603a8ea6e03-11] Harari, 2003 , p. 168-169.

[_6934a4fe393cdc23-12] Erdős, 1966 .