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.
📌 3 Key Takeaways
🎯
Objective & Hypothesis: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.
📊
Key Findings & Data: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.
💡
Conclusion & Impact: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.
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.
Dong, A. (2024). List equitable coloring of planar graphs without $4$- and $6$-cycles when $\Delta(G)=5$. Hacettepe Journal of Mathematics and Statistics, Volume: 53 Issue: 5. https://doi.org/10.15672/hujms.1255155
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland, New York, 1976.
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.
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.
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.
G. Fijavž, M. Juvan, B. Mohar and R. Škrekovki, Planar graphs without cycles of specific lengths, European. J. Combin. 23, 377-388, 2002.
H. A. Kierstead and A. V. Kostochka, Equitable List Coloring of Graphs with Bounded Degree, J. Graph Theory 74 (3), 309-334, 2012.
A. V. Kostochka, M. J. Pelsmajer and D. B.West, A list analogue of equitable coloring, J. Graph Theory 47, 166-177, 2003.
K. W. Lih, Equitable Coloring of Graphs, Springer Science+Business Media, New York, 2013.
Q. Li and Y. H. Bu, Equitable list coloring of planar graphs without 4- and 6-cycles, Discrete Math. 309, 280-287, 2009.
M. F. Pelsmajer, Equitable list coloring for graphs of maximum degree 3, J. Graph Theory 47, 1-8, 2004.
W. F. Wang and K. W. Lih, Equitable list coloring of graphs, Taiwanese J. Math. 8, 747-759, 2004.
X. Zhang and J. L. Wu, On equitable and equitable list coloring of series-parallel graphs, Discrete Math. 311, 800-803, 2011.
J. L. Zhu and Y. H. Bu, Equitable list colorings of planar graphs without short cycles, Theoretical Computer Science 407, 21-28, 2008.
J. L. Zhu and Y. H. Bu, Equitable and equitable list colorings of graphs, Theoret. Comput. Sci. 411, 3873-3876, 2010.
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.