Choosability of the square of planar subcubic graphs with large girth

被引:19
作者
Havet, F. [1 ]
机构
[1] INRIA Sophia Antipolis, UNSA, CNRS, Projet Mascotte, F-06902 Sophia Antipolis, France
关键词
List colouring; Square of a graph; Bounded density; Planar graph;
D O I
10.1016/j.disc.2007.12.100
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We show that the choice number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choice number of the square of a subcubic planar graph with girth at least 9 is at most 6. We then show that the choice number of the square of a subcubic planar graph with girth at least 13 is at most 5. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:3553 / 3563
页数:11
相关论文
共 9 条
[1]  
Borodin O., 1977, ABSTRACTS 4 ALL UNIO, P127
[2]  
CRANSTON DW, 2006, LIST COLORING UNPUB
[3]  
DVORAK Z, 2005, PS985 IMFM
[4]  
Erdos P., 1979, C NUMERANTUM, V26, P125
[5]   A SOLUTION TO A COLORING PROBLEM OF ERDOS,P. [J].
FLEISCHNER, H ;
STIEBITZ, M .
DISCRETE MATHEMATICS, 1992, 101 (1-3) :39-48
[6]   Choosability conjectures and multicircuits [J].
Kostochka, AV ;
Woodall, DR .
DISCRETE MATHEMATICS, 2001, 240 (1-3) :123-143
[7]   A note on 2-facial coloring of plane graphs [J].
Montassier, Mickael ;
Raspaud, Andre .
INFORMATION PROCESSING LETTERS, 2006, 98 (06) :235-241
[8]  
Thomassen C., 2006, SQUARE PLANAR UNPUB
[9]  
WEGNER G., 1977, Technical report