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 NameAffiliation
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
Download times: 78
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  Download reader