Critical graph
|
|
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:
- G has only one component.
- G is finite (direct consequence of [de Bruijn, Erdös 1951])
- δ(G) ≥ k - 1, that is, every vertex is adjacent to at least k - 1 others.
- If G is (k-1)-regular, meaning every vertex is adjacent to exactly k - 1 others, then G is either Kk or an odd cycle. (Brooks 1941)
- 2 m ≥ (k - 1) n + k - 3. (Dirac 1957)
- 2 m ≥ (k - 1) n + [(k - 3)/(k2 - 3)] n. (Gallai 1963)
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.
A double critical graph is a graph in which the deletion of any pair of adjacent vertices leaves a (k-2)-colorable subgraph. One open problem is to determine whether Kk is the only double critical graph. (Jensen, Toft 1995, p. 105)
References
- Brooks, R. L. (1941). On colouring the nodes of a network. Proc. Cambridge Phil. Soc. 37, 194–197.
- de Bruijn, N. G.; Erdös, P. (1951). A colour problem for infinite graphs and a problem in the theory of relations. Nederl. Akad. Wetensch. Proc. Ser. A 54, 371–373. (Indag. Math. 13.)
- Dirac, G. A. (1957). A theorem of R. L. Brooks and a conjecture of H. Hadwiger. Proc. London Math. Soc. (3) 7, 161–195.
- Gallai, T. (1963). Kritische Graphen I. Publ. Math. Inst. Hungar. Acad. Sci. 8, 165–192.
- Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.