A note on list improper coloring of plane graphs |
| |
Authors: | Wei Dong Baogang Xu |
| |
Affiliation: | a School of Mathematics and Computer Science, Nanjing Normal University, Nanjing, 210097, China b Department of Mathematics, Nanjing XiaoZhuang College, Nanjing, 210017, China |
| |
Abstract: | A list-assignment L to the vertices of G is an assignment of a set L(v) of colors to vertex v for every v∈V(G). An (L,d)∗-coloring is a mapping ? that assigns a color ?(v)∈L(v) to each vertex v∈V(G) such that at most d neighbors of v receive color ?(v). A graph is called (k,d)∗-choosable, if G admits an (L,d)∗-coloring for every list assignment L with |L(v)|≥k for all v∈V(G). In this note, it is proved that every plane graph, which contains no 4-cycles and l-cycles for some l∈{8,9}, is (3,1)∗-choosable. |
| |
Keywords: | Improper choosability Plane graph Cycle |
本文献已被 ScienceDirect 等数据库收录! |
|