✦ LIBER ✦
High-Girth Graphs Avoiding a Minor are Nearly Bipartite
✍ Scribed by Anna Galluccio; Luis A. Goddyn; Pavol Hell
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 166 KB
- Volume
- 83
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
✦ Synopsis
Let H be a fixed graph. We show that any H-minor free graph G of high enough girth has circular chromatic number arbitrarily close to two. Equivalently, each such graph G admits a homomorphism to a large odd circuit. In particular, graphs of high girth and of bounded genus, or of bounded tree width, are ``nearly bipartite'' in this sense. For example, any planar graph of girth at least 16 admits a homomorphism to a pentagon. We also obtain tight bounds on the girth of G in a few specific cases of small forbidden minors H.