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: 368 |
Download times: 317 |
Abstract: |
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\}$. |
Citation: |
DOI:10.3770/j.issn:2095-2651.2023.01.003 |
View Full Text View/Add Comment |
|
|
|