Critical graph
Encyclopedia
In general the notion of criticality can refer to any measure.
But in graph theory
, when the term is used without any qualification, it almost always refers to the chromatic number
of a graph
.
Critical graphs are interesting because they are the minimal members in terms of chromatic number, which is a very important measure in graph theory.
More precise definitions follow.
A vertex or an edge is a critical element of a graph G if its deletion would decrease the chromatic number of G.
Obviously such decrement can be no more than 1 in a 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:
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 showed, every k-critical graph may be formed from a complete graph
Kk 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 Kk is the only double-critical k-chromatic graph (Jensen, Toft 1995, p. 105).
But in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, when the term is used without any qualification, it almost always refers to the chromatic number
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
.
Critical graphs are interesting because they are the minimal members in terms of chromatic number, which is a very important measure in graph theory.
More precise definitions follow.
A vertex or an edge is a critical element of a graph G if its deletion would decrease the chromatic number of G.
Obviously such decrement can be no more than 1 in a 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 componentGlossary of graph theoryGraph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
. - G is finite (this is the De Bruijn–Erdős theorem of ).
- δ(G) ≥ k - 1, that is, every vertex is adjacent to at least k - 1 others.
- If G is (k-1)-regularGlossary of graph theoryGraph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
, meaning every vertex is adjacent to exactly k - 1 others, then G is either KkGlossary of graph theoryGraph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
or an odd cycleGlossary of graph theoryGraph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
. This is Brooks' theorem; see ). - 2 m ≥ (k - 1) n + k - 3 .
- 2 m ≥ (k - 1) n + [(k - 3)/(k2 - 3)] 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 .
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 showed, every k-critical graph may be formed from a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
Kk by combining the Hajós construction
Hajós construction
In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after that may be used to construct any critical graph or any graph whose chromatic number is at least some given threshold.-The 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 Kk is the only double-critical k-chromatic graph (Jensen, Toft 1995, p. 105).