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). 

Hits: 349 
Download times: 294 
Abstract: 
An ($\mathcal{O}_{k_1}$, $\mathcal{O}_{k_2}$)partition of a graph $G$ is the partition of $V(G)$ into two nonempty 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\}$. 
Citation: 
DOI:10.3770/j.issn:20952651.2023.01.003 
View Full Text View/Add Comment 


