Research PaperNo Access

On the double-critical graph conjecture

R. Dharmarajan

https://orcid.org/0000-0001-5402-476X

Niels Abel Foundation, 7/538, ‘Vidhyashree’, Karekkaattu Parambu, Ambikapuram P. O., Palakkad, Kerala 678011, India

E-mail Address: mathnafrd@gmail.com

Corresponding author.

Search for more papers by this author

and

D. Ramachandran

Niels Abel Foundation, 7/538, ‘Vidhyashree’, Karekkaattu Parambu, Ambikapuram P. O., Palakkad, Kerala 678011, India

E-mail Address: claudebergedr@gmail.com

Search for more papers by this author

https://doi.org/10.1142/S1793830922501336Cited by:0 (Source: Crossref)

Abstract

A connected graph $G$ is double-critical if the chromatic number of $G - x - y$ is two less than that of $G$ whenever $x$ and $y$ are two adjacent vertices of $G$ . The double-critical graph conjecture states that the complete graphs are the only double-critical graphs. We give a proof of this conjecture for any double-critical graph that contains at least one universal vertex. Using this result we prove the conjecture for all double-critical graphs.

Communicated by Weifan Wang

Keywords:

AMSC: 05C15, 05C69

References

1. B. Albar and D. Goncalves , On triangles in $K_{r}$ -minor free graphs, J. Graph Theory 88(1) (2018) 154–173. Crossref, Google Scholar
2. J. M. Harris, J. L. Hirst and M. J. Mossinghoff , Combinatorics and Graph Theory (Springer, 2008). Crossref, Google Scholar
3. H. Huang and A. Yu, A note on the double-critical graph conjecture, preprint (2016), arXiv:1604.05262. Google Scholar
4. K. Kawarabayashi, A. S. Pedersen and B. Toft , Double-critical graphs and complete minors, Electron. J. Combin. 17 (2010) 1–27. Crossref, Google Scholar
5. N. N. Mozhan , On doubly critical graphs with chromatic number five, Metody Diskretn. Anal. 46 (1987) 50–59. Google Scholar
6. A. S. Pedersen , Complete and almost complete minors in double-critical 8-chromatic graphs, Electron. J. Combin. 18 (2011) 1–17. Crossref, Google Scholar
7. M. Rolek and Z.-X. Song , Clique minors in double-critical graphs, J. Graph Theory 88 (2018) 347–355. Crossref, Google Scholar
8. Z.-X. Song, Erdős-Lovász Tihany conjecture for graphs with forbidden holes, preprint (2018), arXiv:1805.11437. Google Scholar
9. M. Stiebitz , $K_{5}$ is the only double-critical $5$ -chromatic graph, Discrete Math. 64 (1987) 91–93. Crossref, Google Scholar
10. R. R. Stoll , Set Theory and Logic (Courier Corporation, 1979). Google Scholar