mad(G)≤(13)/4的图的均匀染色

doi:10.6040/j.issn.1671-9352.0.2023.303

《山东大学学报(理学版)》 ›› 2025, Vol. 60 ›› Issue (2): 41-50.doi: 10.6040/j.issn.1671-9352.0.2023.303

• • 上一篇

mad(G)≤(13)/4的图的均匀染色

吴弦禧,黄丹君

浙江师范大学数学科学学院, 浙江金华 321004

发布日期:2025-02-14
作者简介:吴弦禧(1999— ),女,硕士研究生,研究方向为组合数学与图论. E-mail:2712400835@qq.com
基金资助:
国家自然科学基金资助项目(12171436)

Equitable coloring of graphs with mad(G)≤(13)/4

WU Xianxi, HUANG Danjun

School of Mathematical Sciences, Zhejiang Normal University, Jinhua 321004, Zhejiang, China

Published:2025-02-14

摘要/Abstract

摘要： 图G的均匀k-染色是图G的一个正常k-点染色且满足任意2个色类的顶点数之差的绝对值至多为1。若G存在一个均匀k-染色,则称G是均匀k-可染的。图G的最大平均度是图G的所有非空子图的平均度的最大值,用mad(G)表示。本文运用权转移的方法证明mad(G)≤(13)/4的图是均匀k-可染的,其中k≥max{Δ(G),6},且Δ(G)是图G的最大度。

关键词: 均匀k-染色, 最大平均度, 权转移方法

Abstract: An equitable k-coloring of a graph G is a proper vertex coloring such that the size of any two color classes differ at most one. The graph G is said to be equitably k-colorable if G has an equitable k-coloring. The maximum average degree is the maximum value of average degree of all nonempty subgraphs of G, denoted by mad(G). In this paper, we utilizes the method of weight transfer to prove that a graph G with mad(G)≤(13)/4 is equitably k-colorable for k≥max{Δ(G),6}, where Δ(G)is the maximum degree of G.

Key words: equitable k-coloring, maximum average degree, discharging method

中图分类号:

O157.5

吴弦禧,黄丹君. mad(G)≤(13)/4的图的均匀染色[J]. 《山东大学学报(理学版)》, 2025, 60(2): 41-50.

WU Xianxi, HUANG Danjun. Equitable coloring of graphs with mad(G)≤(13)/4[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(2): 41-50.

参考文献

[1] MEYER W. Equitable coloring[J]. The American Mathematical Monthly, 1973, 80(8):920-922.
[2] ERDÖS P. Theory of graphs and its applications[M]. Prague: Czechoslovak Academy of Sciences, 1964:159.
[3] HAJNAL A, SZEMERÉDI E. Proof of a conjecture of P. Erdös[J]. Combinatorial Theory and Its Applications, 1969:601-623.
[4] KIERSTEAD H A, KOSTOCHKA A V, MYDLARZ M, et al. A fast algorithm for equitable coloring[J]. Combinatorica, 2010, 30(2):217-224.
[5] CHEN B L, LIH K W, WU P L. Equitable coloring and the maximum degree[J]. European Journal of Combinatorics, 1994, 15(5):443-447.
[6] KIERSTEAD H A, KOSTOCHKA A V. Every 4-colorable graph with maximum degree 4 has an equitable 4-coloring[J]. Journal of Graph Theory, 2012, 71(1):31-48.
[7] CHEN B L, LIH K W. Equitable coloring of trees[J]. Journal of Combinatorial Theory Series B, 1994, 61(1):83-87.
[8] LIH K W, WU P L. On equitable coloring of bipartite graphs[J]. Discrete Mathematics, 1996, 151(1/2/3):155-160.
[9] WANG Weifan. Equitable colorings of line graphs and complete r-partite graphs[J]. Systems Science and Mathematical Sciences, 2000, 13(2):190-194.
[10] KOSTOCHKA A V. Equitable colorings of outerplanar graphs[J]. Discrete Mathematics, 2002, 258(1/2/3):373-377.
[11] KOSTOCHKA A V, NAKPRASIT K. Equitable colourings of d-degenerate graphs[J]. Combinatorics, Probability and Computing, 2003, 12(1):53-60.
[12] ZHANG Yi, YAP Hianpoh. Equitable colorings of planar graphs[J]. Journal of Combinatorial Mathematics and Combinatorial Computing, 1998, 27:97-105.
[13] NAKPRASIT K. Equitable colorings of planar graphs with maximum degree at least nine[J]. Discrete Mathematics, 2012, 312(5):1019-1024.
[14] KOSTOCHKA A, LIN D, XIANG Z M. Equitable coloring of planar graphs with maximum degree at least eight[J]. Discrete Mathematics, 2024, 347(6):113964.
[15] ZHANG X. On equitable colorings of sparse graphs[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2016, 39(1):257-268.
[16] ZHANG X, WANG H J, XU L. Equitable coloring of three classes of 1-planar graphs[J]. Acta Mathematicae Applicatae Sinica: English Series, 2018, 34(2):362-372.
[17] CRANSTON D, MAHMOUD R. Equitable coloring in 1-planar graphs[EB/OL]. http://arxiv.org/abs/2311.14915.
[18] DONG A J, ZOU Q S, LI G J. Equitable and list equitable colorings of graphs with bounded maximum average degree[J]. ARS Comb, 2016, 124:303-311.
[19] DONG A J, ZHANG X. Equitable coloring and equitable choosability of graphs with small maximum average degree[J]. Discussiones Mathematicae Graph Theory, 2018, 38(3):829.
[20] ZHU J L, BU Y H. Equitable list colorings of planar graphs without short cycles[J]. Theoretical Computer Science, 2008, 407(1/2/3):21-28.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

mad(G)≤(13)/4的图的均匀染色

Equitable coloring of graphs with mad(G)≤(13)/4

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

多维度评价

本文评价

推荐阅读 0

[1]	李锦,徐常青. 不含相交三角形IC-可平面图的邻点可区别边染色[J]. 《山东大学学报(理学版)》, 2023, 58(12): 134-139.
[2]	张江悦,徐常青. 最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报（理学版）, 2018, 53(6): 7-10.
[3]	潘文华,徐常青. 一类稀疏图的邻和可区别边色数[J]. 山东大学学报（理学版）, 2017, 52(8): 94-99.
[4]	姚京京, 徐常青. 最大度为3或4的图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2015, 50(02): 9-13.
[5]	张欣1,徐兰2，刘桂真1. 稀疏图的k-森林染色[J]. J4, 2011, 46(4): 1-3.