Critical graph

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.

-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.

, there is an optimal proper coloring in which

is a singleton color class.

by combining the Hajós construction with an operation that identifies two non-adjacent vertices.

The graphs formed in this way always require

[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