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. The decrease in the number of colors cannot be by more than one.

Variations

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. Critical graphs are the minimal members in terms of chromatic number, which is a very important measure in graph theory.

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).
• The minimum degree $\delta (G)$ obeys the inequality $\delta (G)\geq k-1$. That is, every vertex is adjacent to at least $k-1$ others. More strongly, $G$ is $(k-1)$-edge-connected.
• If $G$ is a regular graph with degree $k-1$, meaning every vertex is adjacent to exactly $k-1$ others, then $G$ is either the complete graph $K_{k}$ with $n=k$ vertices, or an odd-length cycle graph. This is Brooks' theorem.
• $2m\geq (k-1)n+k-3$.
• $2m\geq (k-1)n+\lfloor (k-3)/(k^{2}-3)\rfloor n$.
• 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. 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.

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 that identifies two non-adjacent 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. It is an open problem to determine whether $K_{k}$ is the only double-critical $k$-chromatic graph.

See also

• Factor-critical graph

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