List improper colourings of planar graphs

被引:84
作者
Skrekovski, R [1 ]
机构
[1] Univ Ljubljana, Dept Math, Ljubljana 1111, Slovenia
关键词
D O I
10.1017/S0963548399003752
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A graph G is m-choosable with impropriety d, or simply (m,d)*-choosable, if for every list assignment L, where \L(upsilon)\ greater than or equal to m for every upsilon is an element of V(G), there exists an L-colouring of G such that each vertex of G has at most d neighbours coloured with the game colour as itself. We show that every planar graph is (3, 2)*-choosable and every outerplanar graph is (2, 2)*-choosable. We also propose some interesting problems about this colouring.
引用
收藏
页码:293 / 299
页数:7
相关论文
共 20 条
[1]  
BOROWIECKI M, 1997, DISCUSS MATH GRAPH T, V17, P123
[2]  
Borowiecki M., 1995, DISCUSS MATH GRAPH T, V15, P185
[3]  
Cowen L, 1997, J GRAPH THEOR, V24, P205, DOI 10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO
[4]  
2-T
[5]   DEFECTIVE COLORINGS OF GRAPHS IN SURFACES - PARTITIONS INTO SUBGRAPHS OF BOUNDED VALENCY [J].
COWEN, LJ ;
COWEN, RH ;
WOODALL, DR .
JOURNAL OF GRAPH THEORY, 1986, 10 (02) :187-195
[6]  
Erd o P., 1979, Congr. Numer., V26, P125
[7]  
Frick M., 1993, ANN DISCR M, V55, P45
[8]   The complexity of planar graph choosability [J].
Gutner, S .
DISCRETE MATHEMATICS, 1996, 159 (1-3) :119-130
[9]  
Jensen T. R., 1995, Graph Coloring Problems
[10]   ALGORITHMIC COMPLEXITY OF LIST COLORINGS [J].
KRATOCHVIL, J ;
TUZA, Z .
DISCRETE APPLIED MATHEMATICS, 1994, 50 (03) :297-302