Title of article :
Planar graphs without cycles of length from 4 to 7 are 3-colorable
Author/Authors :
Borodin، نويسنده , , O.V. and Glebov، نويسنده , , A.N. and Raspaud، نويسنده , , A. and Salavatipour، نويسنده , , M.R.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2005
Abstract :
Planar graphs without cycles of length from 4 to 7 are proved to be 3-colorable. Moreover, it is proved that each proper 3-coloring of a face of length from 8 to 11 in a connected plane graph without cycles of length from 4 to 7 can be extended to a proper 3-coloring of the whole graph. This improves on the previous results on a long standing conjecture of Steinberg.
Keywords :
3-coloring , Steinbergיs conjecture , Planar graphs
Journal title :
Journal of Combinatorial Theory Series B
Journal title :
Journal of Combinatorial Theory Series B