Title of article :
List 2-facial 5-colorability of plane graphs with girth at least 12
Author/Authors :
Borodin، نويسنده , , O.V. and Ivanova، نويسنده , , A.O.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2012
Pages :
9
From page :
306
To page :
314
Abstract :
A proper vertex coloring of a plane graph is 2-facial if any two different vertices joined by a facial walk of length 2 are colored differently, and it is 2-distance if every two vertices at distance 2 from each other are colored differently. Note that any 2-facial coloring of a subcubic graph is 2-distance. known that every plane graph with girth at least 14 has a 2-facial 5-coloring [M. Montassier, A. Raspaud, A note on 2-facial coloring of plane graphs. Inform. Process. Lett. 98 (6) (2006) 235–241], and that every planar subcubic graph with girth at least 13 has a list 2-distance 5-coloring [F. Havet, Choosability of square of planar subcubic graphs with large girth, Discrete Math. 309 (2009) 3353–3563]. engthen these results by proving the list 2-facial 5-colorability of plane graphs with girth at least 12.
Keywords :
Planar graph , girth , Coloring , 2-distance coloring , 2-facial coloring
Journal title :
Discrete Mathematics
Serial Year :
2012
Journal title :
Discrete Mathematics
Record number :
1599804
Link To Document :
بازگشت