Author/Authors :
John Gimbel، نويسنده , , Carsten Thomassen، نويسنده ,
Abstract :
Combining recent results on colorings and Ramsey theory, we show that if G is a triangle-free graph with e edges then the chromatic number of G is at most ce1/3(log e)−2/3 for some constant c. In a previous paper, we found an upper bound on the chromatic number of a triangle-free graph of genus g. Using the new result, we slightly improve this bound to cg1/3(log g)−2/3. Both bounds are best possible, up to a constant multiple.