List equitable coloring of planar graphs without $4$- and $6$-cycles when $\Delta(G)=5$

Abstract

A graph $G$ is $k$ list equitably colorable, if for any given $k$-uniform list assignment $L$, $G$ is $L$-colorable and each color appears on at most $\lceil\frac{|V(G)|}{k}\rceil$ vertices. In 2009, Li and Bu obtained that for planar graph $G$, if $\Delta(G)\geq6$ and without $4$- and $6$-cycles, then $G$ is $\Delta(G)$ list equitably colorable. In order to further prove the conjecture of list equitable coloring, in this paper, we focus on planar graph with $\Delta(G)=5$, and prove that if $G$ is a planar graph without $4$- and $6$-cycles, then $G$ is $\Delta(G)$ list equitably colorable.

Keywords

• list equitable coloring
• planar graph
• degenerate graph

References

1. [1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland, New York, 1976.
2. [2] A. J. Dong, G. J. Li and G. H. Wang, Equitable and list equitable colorings of planar graphs without 4-cycles, Discrete Math. 313 (15), 1610-1619, 2013.
3. [3] A. J. Dong and X. Zhang, Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree, Discuss. Math. Graph Theory 38, 829-839, 2018.
4. [4] A. J. Dong and J. L. Wu, Equitable Coloring and Equitable Choosability of Planar Graphs without chordal 4- and 6-Cycles, Discrete Math. Theor. Comput. Sci. 21 (3), 1-20, 2019.
5. [5] G. Fijavž, M. Juvan, B. Mohar and R. Škrekovki, Planar graphs without cycles of specific lengths, European. J. Combin. 23, 377-388, 2002.
6. [6] H. A. Kierstead and A. V. Kostochka, Equitable List Coloring of Graphs with Bounded Degree, J. Graph Theory 74 (3), 309-334, 2012.
7. [7] A. V. Kostochka, M. J. Pelsmajer and D. B.West, A list analogue of equitable coloring, J. Graph Theory 47, 166-177, 2003.
8. [8] K. W. Lih, Equitable Coloring of Graphs, Springer Science+Business Media, New York, 2013.

9. [9] Q. Li and Y. H. Bu, Equitable list coloring of planar graphs without 4- and 6-cycles, Discrete Math. 309, 280-287, 2009.
10. [10] M. F. Pelsmajer, Equitable list coloring for graphs of maximum degree 3, J. Graph Theory 47, 1-8, 2004.
11. [11] W. F. Wang and K. W. Lih, Equitable list coloring of graphs, Taiwanese J. Math. 8, 747-759, 2004.
12. [12] X. Zhang and J. L. Wu, On equitable and equitable list coloring of series-parallel graphs, Discrete Math. 311, 800-803, 2011.
13. [13] J. L. Zhu and Y. H. Bu, Equitable list colorings of planar graphs without short cycles, Theoretical Computer Science 407, 21-28, 2008.
14. [14] J. L. Zhu and Y. H. Bu, Equitable and equitable list colorings of graphs, Theoret. Comput. Sci. 411, 3873-3876, 2010.
15. [15] J. L. Zhu, Y. H. Bu and X. Min, Equitable List-Coloring for $C_5$-Free Plane Graphs Without Adjacent Triangles, Graphs Combin. 31 (3), 795-804, 2015.