Article in press
Authors:
Title:
$(I,F)$-partition of planar graphs without cycles of length 4, 6, or 9
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-05-05 , Revised: 2023-09-20 , Accepted: 2023-09-20 , Available online: 2023-10-16 , https://doi.org/10.7151/dmgt.2523
Abstract:
A graph $G$ is $(I,F)$-partitionable if its vertex set can be partitioned into
two parts such that one part is an independent set, and the other induces a
forest. A $k$-cycle is a cycle of length $k$. A 9-cycle $[v_1v_2\cdots v_9]$ of
a plane graph is called special if its interior contains either an edge $v_1v_4$
or a common neighbor of $v_1$, $v_4$, and $v_7$. In this paper, we prove that
every plane graph with neither 4- or 6-cycles nor special 9-cycles is
$(I,F)$-partitionable. As corollaries, for each $k\in\{8,9\}$, every planar
graph without cycles of length from $\{4, 6, k\}$ is $(I,F)$-partitionable and
consequently, they are also signed 3-colorable.
Keywords:
planar graph, $(I,F)$-partition, super-extension, bad cycle, discharging
References:
- O.V. Borodin and A.N. Glebov, On the partition of a planar graph of girth $5$ into an empty and an acyclic subgraph, Diskretn. Anal. Issled. Oper. 8(4) (2001) 34–53, in Russian.
- O.V. Borodin, A.N. Glebov, A. Raspaud and M.R. Salavatipour, Planar graphs without cycles of length from $4$ to $7$ are $3$-colorable, J. Combin. Theory Ser. B 93 (2005) 303–311.
https://doi.org/10.1016/j.jctb.2004.11.001 - O.V. Borodin, A.N. Glebov, M. Montassier and A. Raspaud, Planar graphs without $5$- and $7$-cycles and without adjacent triangles are $3$-colorable, J. Combin. Theory Ser. B 99 (2009) 668–673.
https://doi.org/10.1016/j.jctb.2008.11.001 - 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 - L. Hu and X. Li, Every signed planar graph without cycles of length from $4$ to $8$ is $3$-colorable, Discrete Math. 341 (2018) 513–519.
https://doi.org/10.1016/j.disc.2017.09.019 - T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley, NewYork, 1995).
https://doi.org/10.1002/9781118032497 - L. Jin, Y. Kang, M. Schubert and Y. Wang, Planar graphs without $4$- and $5$-cycles and without ext-triangular $7$-cycles are $3$-colorable, SIAM J. Discrete Math. 31 (2017) 1836–1847.
https://doi.org/10.1137/16M1086418 - Y. Kang, L. Jin and Y. Wang, The $3$-colorability of planar graphs without cycles of length $4$, $6$ and $9$, Discrete Math. 339 (2016) 299–307.
https://doi.org/10.1016/j.disc.2015.08.023 - Y. Kang and E. Steffen, Circular coloring of signed graphs, J. Graph Theory 87 (2018) 135–148.
https://doi.org/10.1002/jgt.22147 - K. Kawarabayashi and C. Thomassen, Decomposing a planar graph of girth $5$ into an independent set and a forest, J. Combin. Theory Ser. B 99 (2009) 674–684.
https://doi.org/10.1016/j.jctb.2008.11.002 - R. Liu and G. Yu, Planar graphs without short even cycles are near-bipartite, Discrete Appl. Math. 284 (2020) 626–630.
https://doi.org/10.1016/j.dam.2020.04.017 - F. Lu, M. Rao, Q. Wang and T. Wang, Planar graphs without normally adjacent short cycles, Discrete Math. 345(10) (2022) 112986.
https://doi.org/10.1016/j.disc.2022.112986 - 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 - E. Máčajová, A. Raspaud, M. Škoviera, The chromatic number of a signed graph, Electron. J. Combin. 23(1) (2016) #P1.14.
https://doi.org/10.37236/4938 - C. Thomassen, Decomposing a planar graph into degenerate graphs, J. Combin. Theory Ser. B 65 (1995) 305–314.
https://doi.org/10.1006/jctb.1995.1057 - C. Thomassen, Decomposing a planar graph into an independent set and $3$-degenerate graph, J. Combin. Theory Ser. B 83 (2001) 262–271.
https://doi.org/10.1006/jctb.2001.2056 - W. 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 - B. Xu, On $3$-colorable plane graphs without $5$- and $7$-cycles, Discrete Math. Algorithms Appl. 1 (2009) 347–353.
https://doi.org/10.1142/S1793830909000270
Close