不含4,6-圈及相邻5圈平面图的顶点划分

吉林大学学报(理学版) ›› 2026, Vol. 64 ›› Issue (5): 1029-1038.

不含4,6-圈及相邻5圈平面图的顶点划分

李松霖, 黄明芳, 胡开洋

武汉理工大学数学与统计学院, 武汉 430070

收稿日期:2026-01-13 出版日期:2026-09-26 发布日期:2026-09-26
通讯作者: 黄明芳 E-mail:ds_hmf@126.com

Vertex Partition of Planar Graphs without 4,6-Cycles and Adjacent 5-Cycles

Li Songlin, Huang Mingfang, Hu Kaiyang

School of Mathematics and Statistics, Wuhan University of Technology, Wuhan 430070, China

Received:2026-01-13 Online:2026-09-26 Published:2026-09-26

摘要/Abstract

摘要： 用权值转移法研究不含4,6-圈的平面图顶点划分问题, 得到了不含相邻5-圈的图G的顶点集可划分为两个子集, 使得每个子集的导出子图均为最大度至多为3的森林, 从而改进了关于不含4,6-圈的平面图存在(F₅,F₅)-划分的结论.

关键词: 森林划分, 权值转移, 顶点染色, 平面图

Abstract: Using the weight transfer method, we studied the vertex-partition problem for planar graphs without 4,6-cycles, and obtained that the vertex set of a graph G without adjacent 5-cycles could be partitioned into two subsets, so that the derived subgraph of each subset was a forest with maximum degree at most 3. This improved the conclusion about the existence of (F₅,F₅)-partition of planar graphs without 4,6-cycles.

Key words: forest partition, weight transfer, vertex coloring, planar graph

中图分类号:

O157.5

李松霖, 黄明芳, 胡开洋. 不含4,6-圈及相邻5圈平面图的顶点划分[J]. 吉林大学学报(理学版), 2026, 64(5): 1029-1038.

Li Songlin, Huang Mingfang, Hu Kaiyang. Vertex Partition of Planar Graphs without 4,6-Cycles and Adjacent 5-Cycles[J]. Journal of Jilin University Science Edition, 2026, 64(5): 1029-1038.

[1]	田京京. 限制度的IC平面图中轻弦4-圈的权和[J]. 吉林大学学报(理学版), 2020, 58(5): 1093-1099.
[2]	张艳. 稀疏图平方图的染色数上界[J]. 吉林大学学报(理学版), 2020, 58(3): 575-589.
[3]	王萃琦, 苗正科. 围长为4的无7-,8-圈和15-圈平面图的3-选色[J]. J4, 2008, 46(04): 658-660.