不含相邻 5--圈的平面图的均匀染色
Equitable Coloring of Planar Graphs without Adjacent 5--Cycles
DOI: 10.12677/AAM.2023.123105, PDF, HTML, 下载: 176  浏览: 259 
作者: 吴弦禧*, 黄丹君：浙江师范大学，数学科学学院，浙江 金华
关键词: 均匀 k-染色；平面图；圈；Equitable k-Coloring； Planar Graph； Cycle
摘要: 图 G 的一个均匀 k-染色是指 G 的一个正常 k-点染色且满足任意两个色类的顶点数之差的绝对值至多为 1 。 若 G 存在一个均匀 k-染色，则称 G 是均匀 k-可染的。 本文将运用权转移方法证明：不含相邻 5−-圈的平面图是均匀 k-可染的，其中 k ≥▏max{∆(G), 5} 且 ∆(G) 是图 G 的最大度。
Abstract: An equitable k-coloring of a graph G is a proper vertex coloring such that the difference in the order of any two color classes is at most one. The graph G is said to be equitably k-colorable if G has an equitable k-coloring. In this paper, we will prove that every planar graph without adjacent 5−-cycles is equitably k-colorable for k ≥ max{∆(G), 5}, where ∆(G) is the maximum degree of G.
文章引用：吴弦禧, 黄丹君. 不含相邻 5--圈的平面图的均匀染色[J]. 应用数学进展, 2023, 12(3): 1035-1044. https://doi.org/10.12677/AAM.2023.123105

参考文献

[1] Meyer, W. (1973) Equitable Coloring. The American Mathematical Monthly, 80, 920-922.
https://doi.org/10.1080/00029890.1973.11993408
[2] Erdo˝s, P. (1964) Problem 9. In: Fielder, M., Ed., Theory of Graphs and Its Applications, Publishing House of the Czechoslovak Academy of Sciences, Prague, 159.
[3] Hajnal, A. and Szemer´edi, E. (1970) Proof of a Conjecture of P. Erdo˝s. In: Erdo˝s, P., R´enyi, and S´os, V., Eds., Combinatorial Theory and Its Applications, North-Holland, Amsterdam, 601-623.
[4] Kierstead, H.A., Kostochka, A.V., Mydlarz, M. and Szemer´edi, E. (2010) A Fast Algorithm for Equitable Coloring. Combinatorica, 30, 217-224.
https://doi.org/10.1007/s00493-010-2483-5
[5] Chen, B.L., Lih, K.W. and Wu, P.L. (1994) Equitable Coloring and the Maximum Degree. European Journal of Combinatorics, 15, 443-447.
https://doi.org/10.1006/eujc.1994.1047
[6] Kierstead, H.A. and Kostochka, A.V. (2012) Every 4-Colorable Graph with Maximum Degree 4 Has an Equitable 4-Coloring. Journal of Graph Theory, 71, 31-48.
https://doi.org/10.1002/jgt.20630
[7] Chen, B.L. and Lih, K.W. (1994) Equitable Coloring of Trees. Journal of Combinatorial The- ory, Series B, 61, 83-87.
https://doi.org/10.1006/jctb.1994.1032
[8] Lih, K.W. and Wu, P.L. (1996) On Equitable Coloring of Bipartite Graphs. Discrete Mathe- matics, 151, 155-160.
https://doi.org/10.1016/0012-365X(94)00092-W
[9] Wang, W.F. and Zhang, K.M. (2000) Equitable Colorings of Line Graphs and Complete r- Partite Graphs. Journal of Systems Science and Complexity, 13, 190-194.
[10] Kostochka, A.V. (2002) Equitable Colorings of Outerplanar Graph. Discrete Mathematics, 258, 373-377.
https://doi.org/10.1016/S0012-365X(02)00538-1
[11] Kostochka, A.V. and Nakprasit, K. (2003) Equitable Colorings of k-Degenerate Graphs. Com- binatorics, Probability and Computing, 12, 53-60.
https://doi.org/10.1017/S0963548302005485 [12] Yap, H.P. and Zhang, Y. (1998) Equitable Colorings of Planar Graphs. Journal of Combina-torial Mathematics and Combinatorial Computing, 27, 97-105.
[12] Nakprasit, K. (2012) Equitable Colorings of Planar Graphs with Maximum Degree at Least Nine. Discrete Mathematics, 312, 1019-1024.
https://doi.org/10.1016/j.disc.2011.11.004
[13] Zhu, J.L. and Bu, Y.H. (2008) Equitable List Colorings of Planar Graphs without Short Cycles. Theoretical Computer Science, 407, 21-28.
https://doi.org/10.1016/j.tcs.2008.04.018
[14] 王维凡, 挂浩. 不含4-和5-圈的平面图的均匀染色[J]. 浙江师范大学学报(自然科学版), 2014, 37(1): 1-6.
[15] Zhu, J.L., Bu, Y.H. and Min, X. (2015) Equitable List-Coloring for C5-Free Plane Graphs without Adjacent Triangles. Graphs and Combinatorics, 31, 795-804.
https://doi.org/10.1007/s00373-013-1396-7
[16] Dong, A.J. and Wu, J.L. (2019) Equitable Coloring and Equitable Choosability of Planar Graphs without Chordal 4- and 6-Cycles. Discrete Mathematics Theoretical Computer Science, 21, 1-21.
[17] Sittitrai, P. and Nakprasit, K. (2022) Planar Graphs without Mutually Adjacent 3-, 5-, and 6-Cycles Are 3-Degenerate. Discrete Mathematics, 345, Article ID: 112942.
https://doi.org/10.1016/j.disc.2022.112942

为你推荐