Title of article :
Many 3-colorings of triangle-free planar graphs
Author/Authors :
Thomassen، نويسنده , , Carsten، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2007
Pages :
16
From page :
334
To page :
349
Abstract :
Grِtzsch proved that every planar triangle-free graph is 3-colorable. We prove that it has at least 2 n 1 / 12 / 20 000 distinct 3-colorings where n is the number of vertices. If the graph has girth at least 5, then it has at least 2 n / 10 000 distinct list-colorings provided every vertex has at least three available colors.
Keywords :
Planar graphs , Many 3-colorings
Journal title :
Journal of Combinatorial Theory Series B
Serial Year :
2007
Journal title :
Journal of Combinatorial Theory Series B
Record number :
1527796
Link To Document :
بازگشت