A note on chromatic number and induced odd cycles (Q1676794): Difference between revisions

Summary: An odd hole is an induced odd cycle of length at least 5. \textit{A. D. Scott} and \textit{P. Seymour} [J. Comb. Theory, Ser. B 121, 68--84 (2016; Zbl 1412.05076)] confirmed a conjecture of \textit{A. Gyárfás} [Colloq. Math. Soc. János Bolyai 10, 801-816 (1975; Zbl 0307.05111)] and proved that if a graph \(G\) has no odd holes then \(\chi(G)\leqslant 2^{2^{\omega(G)+2}}\). \textit{M. Chudnovsky} et al. [J. Comb. Theory, Ser. B 100, No. 3, 313--331 (2010; Zbl 1274.05238)] showed that if \(G\) has neither \(K_4\) nor odd holes then \(\chi(G)\leqslant 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)\leqslant 4\) and \(\chi(G)\leqslant 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 [\textit{M. Plummer} and \textit{X. Zha}, Electron. J. Comb. 21, No. 1, Research Paper P1.34, 9 p. (2014; Zbl 1300.05149)].