首页 | 本学科首页   官方微博 | 高级检索  
     

划分围长至少为6 的平面图为有界大小的分支
引用本文:田春雨,孙磊. 划分围长至少为6 的平面图为有界大小的分支[J]. 数学研究及应用, 2023, 43(1): 16-24
作者姓名:田春雨  孙磊
作者单位:山东师范大学数学与统计学院, 山东 济南 250358
基金项目:国家自然科学基金(Grant No.12071265; 12271331), 山东省自然科学基金(Grant No.ZR202102250232).
摘    要:图$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})$-划分,其中$iin{6,7,8}$和$jin{6,7,8,9}$.

关 键 词:平面图     围长   点划分   权转移方法
收稿时间:2022-01-07
修稿时间:2022-06-25

Partitioning Planar Graphs with Girth at Least $6$ into Bounded Size Components
Chunyu TIAN,Lei SUN. Partitioning Planar Graphs with Girth at Least $6$ into Bounded Size Components[J]. Journal of Mathematical Research with Applications, 2023, 43(1): 16-24
Authors:Chunyu TIAN  Lei SUN
Affiliation:School of Mathematics and Statistics, Shandong Normal University, Shandong 250358, P. R. China
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 $iin{6,7,8}$ and $jin{6,7,8,9}$.
Keywords:planar graph   face   girth   vertex partition   discharging procedure
点击此处可从《数学研究及应用》浏览原始摘要信息
点击此处可从《数学研究及应用》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号