Title of article :
Coloring triangle-free graphs with fixed size
Author/Authors :
John Gimbel، نويسنده , , Carsten Thomassen، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2000
Pages :
3
From page :
275
To page :
277
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.
Journal title :
Discrete Mathematics
Serial Year :
2000
Journal title :
Discrete Mathematics
Record number :
950481
Link To Document :
بازگشت