Critical graph

{{Short description|Undirected graph}} {{distinguish|text=the Critical path method in project management}} right|thumb|250px|On the left-top a vertex critical graph with chromatic number 6; next all the N-1 subgraphs with chromatic number 5.

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 ''<math>k</math>-critical graph'' is a critical graph with chromatic number <math>k</math>. A graph <math>G</math> with chromatic number <math>k</math> is ''<math>k</math>-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 <math>k</math>-critical graph <math>G</math> with <math>n</math> vertices and <math>m</math> edges: * <math>G</math> has only one component. * <math>G</math> is finite (this is the De Bruijn–Erdős theorem).{{r|dbe}} * The minimum degree <math>\delta(G)</math> obeys the inequality <math>\delta(G)\ge k-1</math>. That is, every vertex is adjacent to at least <math>k-1</math> others. More strongly, <math>G</math> is <math>(k-1)</math>-edge-connected.{{r|lovasz}} * If <math>G</math> is a regular graph with degree <math>k-1</math>, meaning every vertex is adjacent to exactly <math>k-1</math> others, then <math>G</math> is either the complete graph <math>K_k</math> with <math>n=k</math> vertices, or an odd-length cycle graph. This is Brooks' theorem.{{r|brooks}} * <math>2m\ge(k-1)n+k-3</math>.{{r|dirac}} * <math>2m\ge (k-1)n+(k-3)/(k^2-3)n</math>.{{r|gallai-1}} * Either <math>G</math> 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 <math>G</math> has at least <math>2k-1</math> vertices.{{r|gallai-2}} More strongly, either <math>G</math> has a decomposition of this type, or for every vertex <math>v</math> of <math>G</math> there is a <math>k</math>-coloring in which <math>v</math> is the only vertex of its color and every other color class has at least two vertices.{{r|stehlik}}

Graph <math>G</math> is vertex-critical if and only if for every vertex <math>v</math>, there is an optimal proper coloring in which <math>v</math> is a singleton color class.

As {{harvtxt|Hajós|1961}} showed, every <math>k</math>-critical graph may be formed from a complete graph <math>K_k</math> by combining the Hajós construction with an operation that identifies two non-adjacent vertices. The graphs formed in this way always require <math>k</math> 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 <math>K_k</math> is the only double-critical <math>k</math>-chromatic graph.{{r|erdos}}

==See also== *Factor-critical graph

==References== {{commons category}} <references>

<ref name=brooks>{{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 }}</ref>

<ref name=dbe>{{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'''.)</ref>

<ref name=dirac>{{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}}</ref>

<ref name=erdos>{{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}}</ref>

<ref name=gallai-1>{{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}}</ref>

<ref name=gallai-2>{{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}}</ref>

<ref name=hajos>{{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}} </ref>

<ref name=lovasz>{{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 }}</ref>

<ref name=stehlik>{{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=}}</ref>

</references>

==Further reading== {{refbegin}} *{{citation|last1=Jensen|first1=T. R.|last2=Toft|first2=B.|isbn=0-471-02865-7|location=New York|publisher=Wiley-Interscience|title=Graph coloring problems|year=1995}} *{{citation|doi=10.1016/j.disc.2008.05.021|last1=Stiebitz|first1=Michael|last2=Tuza|first2=Zsolt|last3=Voigt|first3=Margit|author3-link= Margit Voigt |title=On list critical graphs|journal=Discrete Mathematics|publisher=Elsevier|volume=309|issue=15|date=6 August 2009|pages=4931–4941|doi-access=}} {{refend}}

Category:Graph families Category:Graph coloring