Editing Critical graph

{{Short description|Undirected graph}}
{{distinguish|text=the [[Critical path method]] in project management}}
[[File:Critical graph sample.svg|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 [[Glossary of graph theory|component]].  
* <math>G</math> is finite (this is the [[de Bruijn–Erdős theorem (graph theory)|De Bruijn–Erdős theorem]]).{{r|dbe}}
* The minimum [[degree (graph theory)|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>-[[K-edge-connected graph|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+\lfloor(k-3)/(k^2-3)\rfloor 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}}
{{reflist|refs=

<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}}.  ([[Indagationes Mathematicae|''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}} <!-- Might be in: Bericht 1951-1966: Gesamtregister der Jahrgänge I-XV: Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg. Germany: n.p., 1969. {{GBurl|aqxDAAAAMAAJ}} oclc 578119357 --></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>

}}

==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]]