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

Year 2024, , 1393 - 1400, 15.10.2024

Aijun Dong

https://doi.org/10.15672/hujms.1255155

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

Supporting Institution

National Natural Science Foundation of China

Project Number

NSFC12001332

Thanks

This work was supported by the National Natural Science Foundation of China (Grant No. NSFC12001332). It was also supported by China Postdoctoral Science Foundation Funded Project (Grant No.2014M561909); the Nature Science Foundation of Shandong Province of China (Grant No. ZR2014AM028, ZR2017BA009)

References

• [1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland, New York, 1976.
• [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] 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] 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] G. Fijavž, M. Juvan, B. Mohar and R. Škrekovki, Planar graphs without cycles of specific lengths, European. J. Combin. 23, 377-388, 2002.
• [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] A. V. Kostochka, M. J. Pelsmajer and D. B.West, A list analogue of equitable coloring, J. Graph Theory 47, 166-177, 2003.
• [8] K. W. Lih, Equitable Coloring of Graphs, Springer Science+Business Media, New York, 2013.
• [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] M. F. Pelsmajer, Equitable list coloring for graphs of maximum degree 3, J. Graph Theory 47, 1-8, 2004.
• [11] W. F. Wang and K. W. Lih, Equitable list coloring of graphs, Taiwanese J. Math. 8, 747-759, 2004.
• [12] X. Zhang and J. L. Wu, On equitable and equitable list coloring of series-parallel graphs, Discrete Math. 311, 800-803, 2011.
• [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] J. L. Zhu and Y. H. Bu, Equitable and equitable list colorings of graphs, Theoret. Comput. Sci. 411, 3873-3876, 2010.
• [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.