1. bookVolume 38 (2018): Issue 3 (August 2018)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree

Published Online: 19 Jun 2018
Volume & Issue: Volume 38 (2018) - Issue 3 (August 2018)
Page range: 829 - 839
Received: 10 Oct 2016
Accepted: 16 Feb 2017
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A graph is said to be equitably k-colorable if the vertex set V (G) can be partitioned into k independent subsets V1, V2, . . . , Vk such that ||Vi|−|Vj || ≤ 1 (1 ≤ i, jk). A graph G is equitably k-choosable if, for any given k-uniform list assignment L, G is L-colorable and each color appears on at most |V(G)|k$\left\lceil {{{\left| {V(G)} \right|} \over k}} \right\rceil$ vertices. In this paper, we prove that if G is a graph such that mad(G) < 3, then G is equitably k-colorable and equitably k- choosable where k ≥ max{Δ(G), 4}. Moreover, if G is a graph such that 125${{12} \over 5}$ , then G is equitably k-colorable and equitably k-choosable where k ≥ max{Δ (G), 3}.

Keywords

MSC 2010

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1976).10.1007/978-1-349-03521-2Search in Google Scholar

[2] B.L. Chen, K.W. Lih and P.L. Wu, Equitable coloring and the maximum degree, European J. Combin. 15 (1994) 443–447. doi:10.1006/eujc.1994.104710.1006/eujc.1994.1047Search in Google Scholar

[3] B.L. Chen and K.W. Lih, Equitable coloring of trees, J. Combin. Theory Ser. B 611 (1994) 83–87. doi:10.1006/jctb.1994.103210.1006/jctb.1994.1032Search in Google Scholar

[4] B.L. Chen and C.H. Yen, Equitable Δ-coloring of graphs, Discrete Math. 312 (2012) 1512–1517. doi:10.1016/j.disc.2011.05.02010.1016/j.disc.2011.05.020Search in Google Scholar

[5] A.J. Dong, X. Tan, X. Zhang and G.J. Li, Equitable coloring and equitable choosability of planar graphs without 6- and 7-cycles, Ars Combin. 103 (2012) 333–352.Search in Google Scholar

[6] A.J. Dong, X. Zhang and G.J. Li, Equitable coloring and equitable choosability of planar graphs without 5- and 7-cycles, Bull. Malays. Math. Sci. Soc. 35 (2012) 897–910.Search in Google Scholar

[7] A.J. Dong, G.J. Li and G.H. Wang, Equitable and list equitable colorings of planar graphs without 4-cycles, Discrete Math. 313 (2013) 1610–1619. doi:10.1016/j.disc.2013.04.01110.1016/j.disc.2013.04.011Search in Google Scholar

[8] A.J. Dong, Q.S. Zou and G.J. Li, Equitable and list equitable colorings of graphs with bounded maximum average degree, Ars Combin. 124 (2016) 303–311.Search in Google Scholar

[9] A. Hajnal and E. Szemerédi, Proof of a conjecture of Erdős, in: A. Rényi, V.T. Sós (Eds.), Combinatorial Theory and Its Applications (North-Holland, Amsterdam, 1970) 601–623.Search in Google Scholar

[10] H.A. Kierstead and A.V. Kostochka, Equitable list coloring of graphs with bounded degree, J. Graph Theory 74 (2013) 309–334. doi:10.1002/jgt.2171010.1002/jgt.21710Search in Google Scholar

[11] A.V. Kostochka, M.J. Pelsmajer and D.B.West, A list analogue of equitable coloring, J. Graph Theory 47 (2003) 166–177. doi:10.1002/jgt.1013710.1002/jgt.10137Search in Google Scholar

[12] A.V. Kostochka and K. Nakprasit, Equitable colorings of k-degenerate graphs, Combin. Probab. Comput. 12 (2003) 53–60. doi:10.1017/S096354830200548510.1017/S0963548302005485Search in Google Scholar

[13] A.V. Kostochka and K. Nakprasit, Equitable Δ-colorings of graphs with low average degree, Theoret. Comput. Sci. 349 (2005) 82–91. doi:10.1016/j.tcs.2005.09.03110.1016/j.tcs.2005.09.031Search in Google Scholar

[14] K.W. Lih and P.L. Wu, On equitable coloring of bipartite graphs, Discrete Math. 151 (1996) 155–160. doi:10.1016/0012-365X(94)00092-W10.1016/0012-365X(94)00092-WSearch in Google Scholar

[15] K.W. Lih, Equitable Coloring of Graphs (Springer Science+Business Media, New York, 2013).10.1007/978-1-4419-7997-1_25Search in Google Scholar

[16] Q. Li and Y.H. Bu, Equitable list coloring of planar graphs without 4- and 6-cycles, Discrete Math. 309 (2009) 280–287. doi:10.1016/j.disc.2007.12.07010.1016/j.disc.2007.12.070Search in Google Scholar

[17] R. Luo, J.S. Sereni, D.C. Stephens and G. Yu, Equitable coloring of sparse planar graphs, SIAM J. Discrete Math. 24 (2010) 1572–1583. doi:10.1137/09075180310.1137/090751803Search in Google Scholar

[18] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973) 920–922. doi:10.2307/231940510.2307/2319405Search in Google Scholar

[19] K. Nakprasit, Equitable colorings of planar graphs with maximum degree at least nine, Discrete Math. 312 (2012) 1019–1024. doi:10.1016/j.disc.2011.11.00410.1016/j.disc.2011.11.004Search in Google Scholar

[20] K. Nakprasit and K. Nakprasit, Equitable colorings of planar graphs without short cycles, Theoret. Comput. Sci. 465 (2012) 21–27. doi:10.1016/j.tcs.2012.09.01410.1016/j.tcs.2012.09.014Search in Google Scholar

[21] M.F. Pelsmajer, Equitable list coloring for graphs of maximum degree 3, J. Graph Theory 47 (2004) 1–8. doi:10.1002/jgt.2001110.1002/jgt.20011Search in Google Scholar

[22] W.F. Wang and K.W. Lih, Equitable list coloring of graphs, Taiwanese J. Math. 8 (2004) 747–759. doi:10.11650/twjm/150040771610.11650/twjm/1500407716Search in Google Scholar

[23] W.F. Wang and K.M. Zhang, Equitable colorings of line graphs and complete r-partite graphs, System Sci. Math. Sci. 13 (2000) 190–194.Search in Google Scholar

[24] J.L. Wu and P. Wang, Equtiable coloring planar graphs with large girth, Discrete Math. 308 (2008) 985–990. doi:10.1016/j.disc.2007.08.05910.1016/j.disc.2007.08.059Search in Google Scholar

[25] Z. Yan and W. Wang, Equitable coloring of Kronecker products of complete multi-partite graphs and complete graphs, Discrete Appl. Math. 162 (2014) 328–333. doi:10.1016/j.dam.2013.08.04210.1016/j.dam.2013.08.042Search in Google Scholar

[26] H.P. Yap and Y. Zhang, The equitable Δ-coloring conjecture holds for outerplanar graphs, Bull. Inst. Math. Acad. Sin. 25 (1997) 143–149.Search in Google Scholar

[27] H.-P. Yap and Y. Zhang, Equitable colorings of planar graphs, J. Combin. Math. Combin. Comput. 27 (1998) 97–105.Search in Google Scholar

[28] X. Zhang and J.L. Wu, On equitable and equitable list coloring of series-parallel graphs, Discrete Math. 311 (2011) 800–803. doi:10.1016/j.disc.2011.02.00110.1016/j.disc.2011.02.001Search in Google Scholar

[29] J.L. Zhu and Y.H. Bu, Equitable list colorings of planar graphs without short cycles, Theoret. Comput. Sci. 407 (2008) 21–28. doi:10.1016/j.tcs.2008.04.01810.1016/j.tcs.2008.04.018Search in Google Scholar

[30] J.L. Zhu, Y.H. Bu and X. Min, Equitable list-coloring for C5-free plane graphs without adjacent triangles, Graphs Combin. 31 (2015) 795–804. doi:10.1007/s00373-013-1396-710.1007/s00373-013-1396-7Search in Google Scholar

[31] J.L. Zhu and Y.H. Bu, Equitable and equitable list colorings of graphs, Theoret. Comput. Sci. 411 (2010) 3873–3876. doi:10.1016/j.tcs.2010.06.02710.1016/j.tcs.2010.06.027Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo