A Note on Chromatic Number and Induced Odd Cycles

Baogang Xu, Gexin Yu, Xiaoya Zha

Abstract


An odd hole is an induced odd cycle of length at least 5. Scott and Seymour confirmed a conjecture of Gyárfás and proved that if a graph $G$ has no odd holes then $\chi(G)\le 2^{2^{\omega(G)+2}}$. Chudnovsky, Robertson, Seymour and Thomas showed that if $G$ has neither $K_4$ nor odd holes then $\chi(G)\le 4$. In this note, we show that if a graph $G$ has neither triangles nor quadrilaterals, and has no odd holes of length at least 7, then $\chi(G)\le 4$ and $\chi(G)\le 3$ if $G$ has radius at most $3$, and for each vertex $u$ of $G$, the set of vertices of the same distance to $u$ induces a bipartite subgraph. This answers some questions in Plummer and Zha (2014).

Keywords


Chromatic number; Induced odd cycles

Full Text:

PDF