JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2025, Vol. 60 ›› Issue (2): 41-50.doi: 10.6040/j.issn.1671-9352.0.2023.303

Previous Articles    

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

WU Xianxi, HUANG Danjun   

  1. School of Mathematical Sciences, Zhejiang Normal University, Jinhua 321004, Zhejiang, China
  • Published:2025-02-14

PDF (PC)

3

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

CLC Number: 

  • O157.5
[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.
[1] Jin LI,Changqing XU. Adjacent vertex distinguishing edge coloring of IC-planar graphs without intersecting triangles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 134-139.
[2] ZHANG Jiang-yue, XU Chang-qing. Linear 2-arboricity of graphs with maximum average degree at most 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 7-10.
[3] PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing index of a kind of sparse graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 94-99.
[4] SUN Lin, CAI Hua. On the vertex-arboricity of embedded graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 38-42.
[5] YAO Jing-jing, XU Chang-qing. Neighbor sum distinguishing total coloring of graphs with maximum degree 3 or 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 9-13.
[6] ZHANG Xin1, XU Lan2, LIU Gui-Zhen1. k-forested coloring of sparse graphs [J]. J4, 2011, 46(4): 1-3.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd