Entire choosability of near-outerplane graphs

被引:4
作者
Hetherington, Timothy J. [1 ]
机构
[1] Univ Nottingham, Sch Math Sci, Nottingham NG7 2RD, England
关键词
Outerplanar graph; Minor-free graph; Series-parallel graph; PLANE GRAPHS; CONJECTURE;
D O I
10.1016/j.disc.2008.04.043
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
It is proved that if G is a plane embedding of a K-4-minor-free graph with maximum degree Delta, then G is entirely 7-choosable if Delta <= 4 and G is entirely (Delta + 2)-choosable if Delta >= 5: that is, if every vertex, edge and face of G is given a list of max{7, Delta + 2} colours, then every element can be given a colour from its list such that no two adjacent or incident elements are given the same colour. It is proved also that this result holds if G is a plane embedding of a K-2,K-3-minor-free graph or a ((K) over bar (2) + (K-1 boolean OR K-2))-minor-free graph. As a special case this proves that the Entire Coluring Conjecture, that a plane graph is entirely (6 + 4)colourable, holds if C is a plane embedding of a K4-minor-free graph, a K-2,K-3-minor-free graph or a ((K) over bar (2) + (K-1 boolean OR K-2))-minor-free graph. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:2153 / 2165
页数:13
相关论文
共 20 条
[1]  
Borodin O. V., 1995, B I COMBIN APPL, V14, P87
[2]  
BORODIN OV, 1984, METODY DISKRET ANAL, V41, P12
[3]  
DIRAC G. A., 1952, J. London Math. Soc., Vs1-27, P85, DOI 10.1112/jlms/s1-27.1.85
[4]  
Erdos P., 1979, C NUMERANTUM, V26, P125
[5]  
Hetherington T. J., 2008, B I COMBIN APPL, V54, P33
[6]  
Hetherington T. J., 2006, THESIS U NOTTINGHAM
[7]  
HETHERINGTON TJ, 2006, ELECT J COMBIN, V13
[8]  
HETHERINGTON TJ, ARS COMBIN IN PRESS
[9]  
Kronk H. V., 1973, Discrete Mathematics, V5, P253, DOI 10.1016/0012-365X(73)90142-8
[10]   ENTIRE CHROMATIC NUMBER OF A NORMAL GRAPH IS AT MOST 7 [J].
KRONK, HV ;
MITCHEM, J .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1972, 78 (05) :799-&