田春雨,孙磊.划分围长至少为6 的平面图为有界大小的分支[J].数学研究及应用,2023,43(1):16~24 |
划分围长至少为6 的平面图为有界大小的分支 |
Partitioning Planar Graphs with Girth at Least $6$ into Bounded Size Components |
投稿时间:2022-01-07 修订日期:2022-06-25 |
DOI:10.3770/j.issn:2095-2651.2023.01.003 |
中文关键词: 平面图 面 围长 点划分 权转移方法 |
英文关键词:planar graph face girth vertex partition discharging procedure |
基金项目:国家自然科学基金(Grant No.12071265; 12271331), 山东省自然科学基金(Grant No.ZR202102250232). |
|
摘要点击次数: 319 |
全文下载次数: 274 |
中文摘要: |
图$G$的$(\mathcal{O}_{k_1}, \mathcal{O}_{k_2})$-划分是将$V(G)$划分成两个非空子集$V_{1}$和$V_{2}$, 使得$G[V_{1}]$和$G[V_{2}]$分别是分支的阶数至多$k_1$和$k_2$的图.在本文中,我们考虑了有围长限制的平面图的点集划分问题,使得每个部分导出一个具有有界大小分支的图.我们证明了每一个围长至少为6并且$i$-圈不与$j$-圈相交的平面图允许$(\mathcal{O}_{2}$, $\mathcal{O}_{3})$-划分,其中$i\in\{6,7,8\}$和$j\in\{6,7,8,9\}$. |
英文摘要: |
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\}$. |
查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|