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).
@article{10_37236_5555,
author = {Baogang Xu and Gexin Yu and Xiaoya Zha},
title = {A note on chromatic number and induced odd cycles},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {4},
doi = {10.37236/5555},
zbl = {1373.05071},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5555/}
}
TY - JOUR
AU - Baogang Xu
AU - Gexin Yu
AU - Xiaoya Zha
TI - A note on chromatic number and induced odd cycles
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/5555/
DO - 10.37236/5555
ID - 10_37236_5555
ER -
%0 Journal Article
%A Baogang Xu
%A Gexin Yu
%A Xiaoya Zha
%T A note on chromatic number and induced odd cycles
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/5555/
%R 10.37236/5555
%F 10_37236_5555
Baogang Xu; Gexin Yu; Xiaoya Zha. A note on chromatic number and induced odd cycles. The electronic journal of combinatorics, Tome 24 (2017) no. 4. doi: 10.37236/5555
