Back to Search
Start Over
Homomorphisms of triangle-free graphs without a -minor
- Source :
-
Discrete Mathematics . Sep2009, Vol. 309 Issue 18, p5789-5798. 10p. - Publication Year :
- 2009
-
Abstract
- Abstract: In the course of extending Grötzsch’s Theorem, we prove that every triangle-free graph without a -minor is 3-colorable. It has been recently proved that every triangle-free planar graph admits a homomorphism to the Clebsch graph. We also extend this result to the class of triangle-free graphs without a -minor. This is related to some conjectures which generalize the Four-Color Theorem. While we show that our results cannot be extended directly, we conjecture that every -minor-free graph of girth at least 5 is 3-colorable. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 309
- Issue :
- 18
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 44105950
- Full Text :
- https://doi.org/10.1016/j.disc.2009.04.032