Critical graph explained
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
-critical graph
is a critical graph with chromatic number
. A graph
with chromatic number
is
-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
-critical graph
with
vertices and
edges:
has only one
component.
is finite (this is the
De Bruijn–Erdős theorem).
obeys the inequality
. That is, every vertex is adjacent to at least
others. More strongly,
is
-
edge-connected.
is a
regular graph with degree
, meaning every vertex is adjacent to exactly
others, then
is either the
complete graph
with
vertices, or an odd-length
cycle graph. This is
Brooks' theorem.
.
2m\ge(k-1)n+\lfloor(k-3)/(k2-3)\rfloorn
.
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
has at least
vertices. More strongly, either
has a decomposition of this type, or for every vertex
of
there is a
-coloring in which
is the only vertex of its color and every other color class has at least two vertices.
Graph
is vertex-critical if and only if for every vertex
, there is an optimal proper coloring in which
is a singleton color class.
As showed, every
-critical graph may be formed from a
complete graph
by combining the
Hajós construction with an operation that identifies two non-adjacent vertices. The graphs formed in this way always require
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
is the only double-critical
-chromatic graph.
See also