Coloring triangle-free graphs with fixed size (Q1567684): Difference between revisions

The authors show that if \(G\) is a triangle-free graph having \(e\) edges, then there is a constant \(c\) so that the chromatic number of \(G\) is at most \(ce^{1/3}(\log e)^{-2/3}\); then if \(G\) is a triangle-free graph of genus \(g\), there is a constant \(c\) so that the chromatic number of \(G\) is at most \(cg^{1/3}(\log g)^{-2/3}\). The latter result slightly improves the authors' previous bound [Trans. Am. Math. Soc. 349, No. 11, 4555-4564 (1997; Zbl 0884.05039)]. Both bounds are best possible, up to a constant multiple.