平面图和不含 K5-子式图的弱退化度
Weak Degeneracy of Planar Graphs andK5-Minor-Free Graphs
DOI: 10.12677/AAM.2022.117501, PDF, HTML, 下载: 200  浏览: 348 
作者: 丁萧萧：浙江师范大学，数学与计算机科学学院，浙江 金华
关键词: 退化度；弱退化度；平面图；圈长；权转移；Degeneracy； Weak Degeneracy； Planar Graphs； The Length of Cycles； Discharging
摘要: 图的弱退化度是由Bernshteyn 和Lee 提出的一个新定义，是图的退化度的变形。 根据定义可知，每个 d-退化的图也是 d-弱退化的。 另一方面，如果 G 是弱退化的，那么 χ(G) ≤ χl(G) ≤ χDP (G) ≤ d + 1。 在这篇论文中，我们证明了不含 K5-子式的图是 4-弱退化的；不含4-圈的平面 图是 3-弱退化的；不含4-圈与3-圈相邻的平面图是3-弱退化的。
Abstract: Weak degeneracy of graphs is a new definition proposed by Bernshteyn and Lee. It is the deformation of the degeneracy of graphs. By definition, every d-degenerate graph is also weakly d-degenerate. On the other hand, if G is weakly d-degenerate, then χ(G) ≤ χl(G) ≤ χDP (G) ≤ d + 1. In this paper, we prove that planar graphs with K5-minor-free are weakly 4-degenerate, planar graphs without 4-cycles are weakly 3-degenerate and planar graphs without 4-cycles adjacent to 3-cycles are weakly 3- degenerate.
文章引用：丁萧萧. 平面图和不含 K5-子式图的弱退化度[J]. 应用数学进展, 2022, 11(7): 4760-4773. https://doi.org/10.12677/AAM.2022.117501

参考文献

[1] Vizing, V.G. (1976) Vertex Colorings with Given Colors. Metody Diskretnogo Analiza Novosi- birsk, 29, 3-10. (In Russian)
[2] Erdo˝s, P., Rubin, A.L. and Taylor, H. (1979) Choosability in Graphs. Congressus Numeran- tium, 26, 125-127.
[3] Dvoˇr´ak, Z. and Postle, L. (2018) Correspondence Coloring and Its Application to List-Coloring Planar Graphs without Cycles of Lengths 4 to 8. Journal of Combinatorial Theory, Series B, 129, 38-54.
https://doi.org/10.1016/j.jctb.2017.09.001
[4] Bernshteyn, A. and Kostochka, A. (2018) On Differences between DP-Coloring and List Col- oring. Siberian Advances in Mathematics, 21, 61-71.
[5] Bernshteyn, A. and Lee, E. (2021) Weak Degeneracy of Graphs. arXiv:2111.05908
[6] Thomassen, C. (1994) Every Planar Graph Is 5-Choosable. Journal of Combinatorial Theory, Series B, 62, 190-191.
https://doi.org/10.1006/jctb.1994.1062
[7] Sˇkrekovskiv, R. (1998) Choosability of K5-Minor-Free Graphs. Discrete Mathematics, 190, 223-226.
https://doi.org/10.1016/S0012-365X(98)00158-7
[8] He, W., Miao, W. and Shen, Y. (2008) Another Proof of the 5-Choosability of K5-Minor-Free Graphs. Discrete Mathematics, 308, 4024-4026.
[9] Li, L. and Wang, T. (2022) An Extension of Thomassen’s Result on Choosability. Applied Mathematics and Computation, 425, Article ID: 127100.
https://doi.org/10.1016/j.amc.2022.127100
[10] Lam, P.C.B., Xu, B. and Liu, J. (1999) The 4-Choosability of Plane Graphs without 4-Cycles. Journal of Combinatorial Theory, Series B, 76, 117-126.
https://doi.org/10.1006/jctb.1998.1893
[11] Kim, S.J. and Ozeki, K. (2018) A Sufficient Condition for DP-4-Colorability. Discrete Mathe- matics, 341, 1983-1986.
https://doi.org/10.1016/j.disc.2018.03.027
[12] Cheng, P., Chen, M. and Wang, Y. (2016) Planar Graphs without 4-Cycles Adjacent to Tri- angles Are 4-Choosable. Discrete Mathematics, 339, 3052-3057.
https://doi.org/10.1016/j.disc.2016.06.009
[13] Kim, S.J. and Yu, X. (2019) Planar Graphs without 4-Cycles Adjacent to Triangles Are DP- 4-Colorable. Graphs and Combinatorics, 35, 707-718.
https://doi.org/10.1007/s00373-019-02028-z
[14] Wagner, K. (1937) U¨ ber eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, 114, 570-590.
https://doi.org/10.1007/BF01594196
[15] Wang, W. and Lih, K.W. (2002) Choosability and Edge Choosability of Planar Graphs without Five Cycles. Applied Mathematics Letters, 15, 561-565.
https://doi.org/10.1016/S0893-9659(02)80007-6
[16] Fijavˇz, G., Juvan, M., Mohar, B. and Sˇkrekovski, R. (2002) Planar Graphs without Cycles of Specific Lengths. European Journal of Combinatorics, 23, 377-388.
https://doi.org/10.1006/eujc.2002.0570

为你推荐