In this paper, we study the problem of partitioning the vertex set of a planar graph with girth restriction into parts, also referred to as color classes, such that each part induces a graph with components of bounded order. An ($ \mathcal{I} $, $ \mathcal{O}_{k} $)-partition of a graph $ G $ is the partition of $ V(G) $ into two non-empty subsets $ V_{1} $ and $ V_{2} $, such that $ G[V_{1}] $ is an edgeless graph and $ G[V_{2}] $ is a graph with components of order at most $ k $. We prove that every planar graph with girth 9 and without intersecting $ 9 $-face admits an ($ \mathcal{I} $, $ \mathcal{O}_{6} $)-partition. This improves a result of Choi, Dross and Ochem (2020) which says every planar graph with girth at least $ 9 $ admits an ($ \mathcal{I} $, $ \mathcal{O}_{9} $)-partition.
Citation: Chunyu Tian, Lei Sun. Partitioning planar graphs with girth at least $ 9 $ into an edgeless graph and a graph with bounded size components[J]. Mathematical Modelling and Control, 2021, 1(3): 136-144. doi: 10.3934/mmc.2021012
In this paper, we study the problem of partitioning the vertex set of a planar graph with girth restriction into parts, also referred to as color classes, such that each part induces a graph with components of bounded order. An ($ \mathcal{I} $, $ \mathcal{O}_{k} $)-partition of a graph $ G $ is the partition of $ V(G) $ into two non-empty subsets $ V_{1} $ and $ V_{2} $, such that $ G[V_{1}] $ is an edgeless graph and $ G[V_{2}] $ is a graph with components of order at most $ k $. We prove that every planar graph with girth 9 and without intersecting $ 9 $-face admits an ($ \mathcal{I} $, $ \mathcal{O}_{6} $)-partition. This improves a result of Choi, Dross and Ochem (2020) which says every planar graph with girth at least $ 9 $ admits an ($ \mathcal{I} $, $ \mathcal{O}_{9} $)-partition.
| [1] | K. Appel, W. Haken, Every planar map is four colorable, part I. Discharging, Illinois J. Math., 21 (1977), 429–490. |
| [2] | K. Appel, W. Haken, Every planar map is four colorable, part II. Reducibility, Illinois J. Math., 21 (1977), 491–567. |
| [3] |
I. Choi, F. Dross, P. Ochem, Partitioning sparse graphs into an independent set and a graph with bounded size components, Discrete Mathematics, 343 (2020), 111921. doi: 10.1016/j.disc.2020.111921
|
| [4] |
O.V. Borodin, A.V. Kostochka, M. Yancey, On 1-improper 2-coloring of sparse graphs, Discrete Math., 313 (2013), 2638–2649 doi: 10.1016/j.disc.2013.07.014
|
| [5] |
N. Alon, G. Ding, B. Oporowski, D. Vertigan, Partitioning into graphs with only small components, J. Combin. Theory Ser. B, 87 (2003), 231–243. doi: 10.1016/S0095-8956(02)00006-0
|
| [6] |
K.S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory, 14 (1990), 73–75. doi: 10.1002/jgt.3190140108
|
| [7] | O.V. Borodin, A.N. Glebov, On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph, Diskretn. Anal. Issled. Oper. Ser. 1, 8 (2001), 34–53. |
| [8] | O.V. Borodin, A proof of B. Grünbaum's conjecture on the acyclic $5$-colorability of planar graphs, Dokl. Akad. Nauk SSSR, 231 (1976), 18–20. |
| [9] |
F. Dross, M. Montassier, A. Pinlou, Partitioning a triangle-free planar graph into a forest and a forest of bounded degree, European J. Combin., 66 (2017), 81–94. doi: 10.1016/j.ejc.2017.06.014
|
Chunyu Tian, Lei Sun. Partitioning planar graphs with girth at least $ 9 $ into an edgeless graph and a graph with bounded size components[J]. Mathematical Modelling and Control, 2021, 1(3): 136-144. doi: 10.3934/mmc.2021012
DownLoad: