Article in press
Authors:
Title:
Vertex partitions of (C4, C5, C10)-free graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-06-05 , Revised: 2025-01-14 , Accepted: 2025-01-14 , Available online: 2025-01-29 , https://doi.org/10.7151/dmgt.2577
Abstract:
A graph $G$ is improperly $(d_1, d_2,\dots,d_k)$-colorable or just
$(d_1, d_2,\dots,d_k)$-colorable if its vertices can be partitioned
into $k$ subsets $V_1, V_2, \dots, V_k$ such that $\Delta(G[V_i])\leq d_i$
for $1\leq i\leq k$. It is known that every $(C_4, C_i, C_j)$-free planar
graph is $(1, 0, 0)$-colorable whenever $5\leq i<j\leq 9$. In this paper, we
prove that every $(C_4, C_5, C_{10})$-free planar graph is $(1, 0, 0)$-colorable.
Keywords:
planar graph, improper coloring, Steinberg conjecture, cycle
References:
- V. Cohen-Addad, M. Hebdige, D. Král, Z. Li and E. Salgado, Steinberg's Conjecture is false, J. Combin. Theory Ser. B 122 (2017) 452–456.
https://doi.org/10.1016/j.jctb.2016.07.006 - K. Appel and W. Haken, Every planar map is four colorable, Part I. Discharging, Illinois J. Math. 21 (1977) 429–490.
https://doi.org/10.1215/ijm/1256049011 - K. Appel, W. Haken and J. Koch, Every planar map is four colorable, Part II. Reducibilituy, Illinois J. Math. 21 (1977) 491–567.
https://doi.org/10.1215/ijm/1256049012 - J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).
https://doi.org/10.1007/978-1-84628-970-5 - Y. Bu, J. Xu and Y. Wang, $(1, 0, 0)$-colorability of planar graphs without prescribed short cycles, J. Comb. Optim. 30 (2015) 627–646.
https://doi.org//10.1007/s10878-013-9653-5 - M. Chen, Y. Wang, P. Liu and J. Xu, Planar graphs without cycles of length $4$ or $5$ are $(2, 0, 0)$-colorable, Discrete Math. 339 (2016) 886–905.
https://doi.org//10.1016/j.disc.2015.10.029 - Y. Kang, L. Jin, P. Liu and Y. Wang, $(1,0,0)$-colorability of planar graphs without cycles of length $4$ or $6$, Discrete Math. 345 (2022) 112758.
https://doi.org//10.1016/j.disc.2021.112758 - H. Lu, Y. Wang, W. Wang, Y. Bu, M. Montassier and A. Raspaud, On the $3$-colorability of planar graphs without $4$-, $7$- and $9$-cycles, Discrete Math. 309 (2009) 4596–4607.
https://doi.org//10.1016/j.disc.2009.02.030 - S.A. Mondal, Planar graphs without $4$-, $5$- and $8$-cycles are $3$-colorable, Discuss. Math. Graph Theory 31 (2011) 775–789.
https://doi.org/10.7151/dmgt.1579 - W.-F. Wang and M. Chen, Planar graphs without $4$, $6$, $8$-cycles are $3$-colorable, Sci. China Math. 50 (2007) 1552–1562.
https://doi.org/10.1007/s11425-007-0106-4 - Y. Wang and Y. Yang, $(1, 0, 0)$-colorability of planar graphs without cycles of length $4$, $5$ or $9$, Discrete Math. 326 (2014) 44–49.
https://doi.org//10.1016/j.disc.2014.03.001 - B. Xu, On $3$-colorable plane graphs without $5$- and $7$-cycles, J. Combin. Theory Ser. B 96 (2006) 958–963.
https://doi.org//10.1016/j.jctb.2006.02.005
Close