Critical graph

File:Critical graph sample.svg

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 <math>k</math>-critical graph is a critical graph with chromatic number <math>k</math>. A graph <math>G</math> with chromatic number <math>k</math> is <math>k</math>-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 <math>k</math>-critical graph <math>G</math> with <math>n</math> vertices and <math>m</math> edges:

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

Graph <math>G</math> is vertex-critical if and only if for every vertex <math>v</math>, there is an optimal proper coloring in which <math>v</math> is a singleton color class.

As Template:Harvtxt showed, every <math>k</math>-critical graph may be formed from a complete graph <math>K_k</math> by combining the Hajós construction with an operation that identifies two non-adjacent vertices. The graphs formed in this way always require <math>k</math> colors in any proper coloring.Template:R

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 <math>K_k</math> is the only double-critical <math>k</math>-chromatic graph.Template:R

See also

• Factor-critical graph

Further reading

• Template:Citation
• Template:Citation