不含相邻短圈的平面图的 (3, 1)*-可选性
(3, 1)*-Choosability of Planar Graphs without Adjacent Short Cycles

作者: 张 倩 :浙江师范大学,数学与计算机科学学院,浙江 金华;

关键词: 平面图非正常列表染色权转移Planar Graph Improper Choosability Discharge Cycle

摘要:
图 G的一个颜色列表配置 L是指给 G中的每个顶点 v都分配一个可用色集 L(v)。 如果在映射 ϕ下对任意 v ∈ V (G)均满足 ϕ(v) ∈ L(v),使得在 v的邻点中至多有 d个顶点的颜色为 ϕ(v),那 么我们称 G是 (L, d)-可染的。 如果对任意颜色列表配置 L = {L(v)||L(v)| ≥ k, v ∈ V (G)}, G都 是 (L, d)-可染的,那么我们就称 G 是 (k, d)-可选的。 Xu 和Zhang 猜想:不含相邻 3-圈的平 面图是 (3, 1)-可选的。 在本文中,我们将证明不含相邻 k-圈的平面图是 (3, 1)-可选的,其中k ∈ {3, 4, 5}。

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.


Abstract:

文章引用: 张 倩 (2019) 不含相邻短圈的平面图的 (3, 1)*-可选性。 应用数学进展, 8, 1574-1586. doi: 10.12677/AAM.2019.89184

参考文献

[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

分享
Top