Critical graph

{{distinguish|text=the Critical path method in project management}}

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 $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).{{r|dbe}}
The minimum degree $\delta(G)$ obeys the inequality $\delta(G)\ge k-1$ . That is, every vertex is adjacent to at least $k-1$ others. More strongly, $G$ is $(k-1)$ -edge-connected.{{r|lovasz}}
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.{{r|brooks}}
$2m\ge(k-1)n+k-3$ .{{r|dirac}}
$2m\ge (k-1)n+\lfloor(k-3)/(k^2-3)\rfloor n$ .{{r|gallai-1}}
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.{{r|gallai-2}} 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.{{r|stehlik}}

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 {{harvtxt|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.{{r|hajos}}

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.{{r|erdos}}

References

{{reflist|refs=

{{citation|doi=10.1017/S030500410002168X|last1=Brooks|first1=R. L.|journal=Proceedings of the Cambridge Philosophical Society|pages=194–197|issue=2|title=On colouring the nodes of a network|volume=37|year=1941|bibcode=1941PCPS...37..194B |s2cid=209835194 }}

{{citation|last1=de Bruijn|first1=N. G.|author1-link=Nicolaas Govert de Bruijn|last2=Erdős|first2=P.|author2-link=Paul Erdős|journal=Nederl. Akad. Wetensch. Proc. Ser. A|pages=371–373|title=A colour problem for infinite graphs and a problem in the theory of relations|volume=54|year=1951|doi=10.1016/S1385-7258(51)50053-7|url=https://research.tue.nl/nl/publications/a-colour-problem-for-infinite-graphs-and-a-problem-in-the-theory-of-relations(8bb2b225-bd1a-4924-97ee-0eefca35f01b).html|citeseerx=10.1.1.210.6623}}. (Indag. Math. 13.)

{{citation|doi=10.1112/plms/s3-7.1.161|last=Dirac|first=G. A.|author-link=Gabriel Andrew Dirac|journal=Proceedings of the London Mathematical Society|pages=161–195|title=A theorem of R. L. Brooks and a conjecture of H. Hadwiger|issue=1|volume=7|year=1957}}

{{citation|last=Erdős|first=Paul|author-link=Paul Erdős|contribution=Problem 2|page=361|publisher=Proc. Colloq., Tihany|title=In Theory of Graphs|year=1967}}

{{citation|last=Gallai|first=T.|author-link=Tibor Gallai|journal=Publ. Math. Inst. Hungar. Acad. Sci.|pages=165–192|title=Kritische Graphen I|volume=8|year=1963|ref=none}}

{{citation|last=Gallai|first=T.|author-link=Tibor Gallai|journal=Publ. Math. Inst. Hungar. Acad. Sci.|pages=373–395|title=Kritische Graphen II|volume=8|year=1963|ref=none}}

{{citation|last=Hajós|first=G.|author-link=György Hajós|title=Über eine Konstruktion nicht {{mvar|n}}-färbbarer Graphen|journal=Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe|volume=10|pages=116–117|year=1961}}

{{citation|last=Lovász|first=László|author-link=László Lovász|contribution=Solution to Exercise 9.21|publisher=North-Holland|title=Combinatorial Problems and Exercises |edition=2nd |year=1992 |isbn=978-0-8218-6947-5 }}

{{citation|last=Stehlík|first=Matěj|doi=10.1016/S0095-8956(03)00069-8|issue=2|journal=Journal of Combinatorial Theory|mr=2017723|pages=189–194|series=Series B|title=Critical graphs with connected complements|volume=89|year=2003|doi-access=}}

}}

Critical graph

Variations

See also

References

Further reading