K4‐free graphs with no odd hole: Even pairs and the circular chromatic number |
| |
Authors: | Yori Zwols |
| |
Affiliation: | Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027 |
| |
Abstract: | An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K4‐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 K4‐free graph with no odd hole has circular chromatic number strictly smaller than 4. We also exhibit a sequence {Hn} of such graphs with limn→∞χc(Hn)=4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 303–322, 2010 |
| |
Keywords: | forbidden induced subgraphs circular chromatic number even pairs odd holes |
|
|