Circumference, chromatic number and online coloring (Q2439828)

Denote in a graph \(G\) the length of the longest odd cycle by \(\ell(G)\), and the chromatic number by \(\chi(G)\). The authors address a conjecture of \textit{P. Erdős} [Ann. Discrete Math. 51, 69--79 (1992; Zbl 0760.05025)] that a triangle-free graph of chromatic number \(k\geq3\) contains an odd cycle of length at least \(k^{2-o(1)}\). Theorem 7. If \(G\) is a triangle-free graph, then \(\chi\leq\frac{15\ell}{\log\log\ell}\). Theorem 10. If \(G\) is a triangle-free graph with no \(C_5\) subgraph, then \(\chi\leq6\sqrt{\ell}\). Theorem 12. If \(G\) is a triangle-free graph on \(n\) vertices, then \(\chi\leq\)O\(\left(\sqrt{\frac{\ell}{\log\ell}}\cdot\log n\right)\). Theorem 13. Let \(k\) be a positive integer. If a graph \(G\) has at most \(r\) cycles of different lengths, each \(1\bmod k\), then \(\chi(G)\leq rk+k\). Theorem 14. Let \(k\) be a non-negative integer. If a graph \(G\) has at most \(s\) cycles of different lengths \(2 \bmod k\), then \(\chi(G)\leq sk+k+1\). Theorem 15. If \(G\) is a graph with no cycles of length \(3 \bmod k\), then \(G\) is \(2k\)-colorable. From the authors' abstract: ``Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm''.