#### 期刊菜单

(3, 1)*-Choosability of Planar Graphs without Adjacent Short Cycles
DOI: 10.12677/AAM.2019.89184, PDF, HTML, 下载: 937  浏览: 3,432

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.

 [1] Sˇkrekovski, R. (1999) List Improper Coloring of Planar Graphs. Combinatorics, Probability and Computing, 8, 293-299. https://doi.org/10.1017/S0963548399003752 [2] Eaton, N. and Hull, T. (1999) Defective List Colorings of Planar Graphs. Bulletin of the Institute of Combinatorics and Its Applications, 25, 79-87. [3] 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. https://doi.org/10.1002/jgt.3190100207 [4] Sˇkrekovski, R. (1999) Gr¨ostzsch-Type Theorem for List Colorings with Impropriety One. Com- binatorics, Probability and Computing, 8, 493-507. https://doi.org/10.1017/S096354839900396X [5] Lih, K.W. (2001) A Note on List Improper Coloring Planar Graphs. Applied Mathematics Letters, 14, 269-273. https://doi.org/10.1016/S0893-9659(00)00147-6 [6] Dong, W. and Xu, B. (2009) A Note on List Improper Coloring of Plane Graphs. Discrete Applied Mathematics, 157, 433-436. https://doi.org/10.1016/j.dam.2008.06.023 [7] Wang, Y. and Xu, L. (2013) Improper Choosability of Planar Graphs without 4-Cycles. SIAM Journal on Discrete Mathematics, 27, 2029-2037. https://doi.org/10.1137/120885140 [8] Xu, B. and Zhang, H. (2007) Every Toroidal Graphs without Adjacent Triangles Is (4, 1)∗- Choosable. Discrete Applied Mathematics, 155, 74-78. https://doi.org/10.1016/j.dam.2006.04.042