Partitioning Planar Graphs with Girth at Least $6$ into Bounded Size Components
Received:January 07, 2022  Revised:June 25, 2022
Key Words: planar graph   face   girth   vertex partition   discharging procedure
Fund Project:Supported by the National Natural Science Foundation of China (Grant Nos.12071265; 12271331) and the Natural Science Foundation of Shandong Province (Grant No.ZR202102250232).
 Author Name Affiliation Chunyu TIAN School of Mathematics and Statistics, Shandong Normal University, Shandong 250358, P. R. China Lei SUN School of Mathematics and Statistics, Shandong Normal University, Shandong 250358, P. R. China
Hits: 52
An ($\mathcal{O}_{k_1}$, $\mathcal{O}_{k_2}$)-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}]$ and $G[V_{2}]$ are graphs with components of order at most $k_1$ and $k_2$, respectively. In this paper, we consider the problem of partitioning the vertex set of a planar graph with girth restriction such that each part induces a graph with components of bounded order. We prove that every planar graph with girth at least $6$ and $i$-cycle is not intersecting with $j$-cycle admits an ($\mathcal{O}_{2}$, $\mathcal{O}_{3}$)-partition, where $i\in\{6,7,8\}$ and $j\in\{6,7,8,9\}$.