Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649478 | Discrete Mathematics | 2009 | 10 Pages |
Abstract
In the course of extending Grötzsch’s Theorem, we prove that every triangle-free graph without a K5K5-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 K5K5-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 K6K6-minor-free graph of girth at least 5 is 3-colorable.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Reza Naserasr, Yared Nigussie, Riste Škrekovski,