High-girth cubic graphs are homomorphic to the Clebsch graph
✍ Scribed by Matt DeVos; Robert Šámal
- Publisher
- John Wiley and Sons
- Year
- 2011
- Tongue
- English
- Weight
- 192 KB
- Volume
- 66
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5-colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1). Hopkins and Staton [J Graph Theory 6(2) (1982), 115-121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477-504] proved that every (sub)cubic graph of girth at least 4 has an edge-cut containing at least 4 5 of the edges. The existence of such an edge-cut follows immediately Contract grant sponsor: Ministry of Education of the Czech Republic; Contract grant number: Project 1M0545 (to R. Š.). Partially supported by grant GA CR p201/10/p337.U