Geodesic
Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 829-839.

Voir la notice de l'article provenant de la source Library of Science

A graph is said to be equitably k-colorable if the vertex set V (G) can be partitioned into k independent subsets V_1, V_2, . . ., V_k such that | | V_i |−| V_j | | ≤ 1 (1 ≤ i, j ≤ k). 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 vertices. In this paper, we prove that if G is a graph such that mad(G) lt; 3, then G is equitably k-colorable and equitably k- choosable where k ≥max{Δ (G), 4 }. Moreover, if G is a graph such that mad(G) lt; 12/5, then G is equitably k-colorable and equitably k-choosable where k ≥max{Δ (G), 3 }.
Keywords: graph coloring, equitable choosability, maximum average degree 
@article{DMGT_2018_38_3_a12,
     author = {Dong, Aijun and Zhang, Xin},
     title = {Equitable {Coloring} and {Equitable} {Choosability} of {Graphs} with {Small} {Maximum} {Average} {Degree}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {829--839},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a12/}
}
TY  - JOUR
AU  - Dong, Aijun
AU  - Zhang, Xin
TI  - Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 829
EP  - 839
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a12/
LA  - en
ID  - DMGT_2018_38_3_a12
ER  - 
%0 Journal Article
%A Dong, Aijun
%A Zhang, Xin
%T Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 829-839
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a12/
%G en
%F DMGT_2018_38_3_a12
Dong, Aijun; Zhang, Xin. Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 829-839. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a12/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1976).

[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.1047

[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.1032

[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.020

[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.

[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.

[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.011

[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.

[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.

[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.21710

[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.10137

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

[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.031

[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-W

[15] K.W. Lih, Equitable Coloring of Graphs (Springer Science+Business Media, New York, 2013).

[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.070

[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/090751803

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

[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.004

[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.014

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

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

[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.

[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.059

[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.042

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

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

[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.001

[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.018

[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-7

[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.027