不含相邻短圈的平面图的 (3, 1)*-可选性
(3, 1)*-Choosability of Planar Graphs without Adjacent Short Cycles
作者: 张 倩 ：浙江师范大学，数学与计算机科学学院，浙江 金华;
Abstract: For a graph G, a list assignment is a function L that assigns a list L(v) of colors to each vertex v ∈ V (G). An (L, d)-coloring is a mapping ϕ that assigns a color ϕ(v) ∈ L(v) to each v ∈ V (G) so that at most d neighbors of v receive the color ϕ(v). A graph G is said to be (k, d)∗-choosable if it admits an (L, d)∗-coloring for every list assignment L with|L(v)| ≥ k for all v ∈ V (G). Xu and Zhang conjectured that every planar graph without adjacent 3-cycles is (3, 1)∗-choosable. In this paper, we prove that every planar graph without adjacent k-cycles, k = 3, 4, 5, is (3, 1)∗-choosable.
文章引用: 张 倩 (2019) 不含相邻短圈的平面图的 (3, 1)*-可选性。 应用数学进展， 8， 1574-1586. doi: 10.12677/AAM.2019.89184
Sˇkrekovski, R. (1999) List Improper Coloring of Planar Graphs. Combinatorics, Probability and Computing, 8, 293-299.
 Eaton, N. and Hull, T. (1999) Defective List Colorings of Planar Graphs. Bulletin of the Institute of Combinatorics and Its Applications, 25, 79-87.
Cowen, L.J., Cowen, R.H. and Woodall, D.R. (1986) Defective Colorings of Graphs in Surfaces: Partitions into Subgraphs of Bounded Valency. Journal of Graph Theory, 10, 187-195.
Sˇkrekovski, R. (1999) Gr¨ostzsch-Type Theorem for List Colorings with Impropriety One. Com- binatorics, Probability and Computing, 8, 493-507.
Lih, K.W. (2001) A Note on List Improper Coloring Planar Graphs. Applied Mathematics Letters, 14, 269-273.
Dong, W. and Xu, B. (2009) A Note on List Improper Coloring of Plane Graphs. Discrete Applied Mathematics, 157, 433-436.
Wang, Y. and Xu, L. (2013) Improper Choosability of Planar Graphs without 4-Cycles. SIAM Journal on Discrete Mathematics, 27, 2029-2037.
Xu, B. and Zhang, H. (2007) Every Toroidal Graphs without Adjacent Triangles Is (4, 1)∗- Choosable. Discrete Applied Mathematics, 155, 74-78.