✦ LIBER ✦
K4-free graphs with no odd hole: Even pairs and the circular chromatic number
✍ Scribed by Yori Zwols
- Publisher
- John Wiley and Sons
- Year
- 2010
- Tongue
- English
- Weight
- 219 KB
- Volume
- 65
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K 4 -free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K 4 -free graph with no odd hole has circular chromatic number strictly smaller than 4. We also exhibit a sequence {H n } of such graphs with lim n→∞ c (H n ) = 4. ᭧ 2010 Wiley