Critical Graph

A critical graph is a graph in which every vertex or edge is a critical element. 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.

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.
• 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 (1941)).
• 2 m ≥ (k − 1) n + k − 3 (Dirac 1957).
• 2 m ≥ (k − 1) n + 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).

It is fairly easy to see that a 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 of identifying two nonadjacent 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 (Jensen, Toft 1995, p. 105).