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

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

摘要

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

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 (($\mathscr{F}_{5}$,$\mathscr{F}_{5}$)-partition of planar graphs without 4,6-cycles.

关键词

森林划分 / 权值转移 / 顶点染色 / 平面图

Key words

forest partition / weight transfer / vertex coloring / planar graph

参考文献

[1] Steinberg R. The State of the Three Color Problem[J]. Annals of Discrete Mathematics, 1993, 55: 211-248.

[2] Cohen-Addad V, Hebdige M, Král’ D, et al. Steinberg’s Conjecture Is False[J]. Journal of Combinatorial Theory: Series B, 2017, 122: 452-456.

[3] Sittitrai P, Nakaprasit K. Defective 2-Colorings of Planar Graphs without 4-Cycles and 5-Cycles[J]. Discrete Mathematics, 2018, 341(8): 2142-2150.

[4] Liu J, Lv J B. Every Planar Graph without 4-Cycles and 5-Cycles Is (2,6)-Colorable[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2020, 43(3): 2493-2507.

[5] Li X W, Liu J, Lv J B. Every Planar Graph without 4-Cycles and 5-Cycles Is (3,3)-Colorable[J]. Graphs and Combinatorics, 2023, 39(6): 118-1-118-19.

[6] Liu Y H, Xiao M Y. The (3,3)-Colorability of Planar Graphs without 4-Cycles and 5-Cycles[J]. Discrete Mathematics, 2023, 346(4): 113306-1-113306-12.

[7] Li X W, Niu L, Tian F Y. On the Strong Bordeaux Conjecture[J]. Discrete Mathematics, 2026, 349(3): 114818-1-114818-20.

[8] Cho E K, Choi I, Park B. Partitioning Planar Graphs without 4-Cycles and 5-Cycles into Bounded Degree Forests[J]. Discrete Mathematics, 2021, 344(1): 112172-1-112172-9.

[9] Lv F, Liang Z S, Liao D Z. Planar Graphs without 4-,5-,7-Cycles and Special 9-Cycles Are Near-Bipartite[J/OL]. Discrete Mathematics, Algorithms and Applications, (2025-10-27)[2025-12-30]. https://doi.org/10.1142/S1793830925501460.

[10] Kang Y L, Lu H K, Jin L G. (I,F)-Partition of Planar Graphs without Cycles of Length 4,6, or 9[J]. Discussiones Mathematicae Graph Theory, 2025, 45(1): 129-150.

[11] Sittitrai P, Nakprasit K M, Nakprasit K. Partitioning Planar Graphs without Specific Cycles into a Forest and a Disjoint Union of Paths[J/OL]. Axioms, (2025-04-14)[2025-12-30]. https://doi.org/10.3390/axioms14040293.

[12] Ma J Q, Huang M F, Zhang X X. Every Planar Graph without 4-Cycles and 6-Cycles Is (2,9)-Colorable[J]. Italian Journal of Pure and Applied Mathematic, 2022, 48: 659-670.

[13] Nakaprasit K, Sittitrai P, Pimpasalee W. Planar Graphs without 4- and 6-Cycles Are (3,4)-Colorable[J]. Discrete Applied Mathematics, 2024, 356: 44-51.

[14] Huang X J, Huang Z W, Lv J B. Partitioning Planar Graphs without 4-Cycles and 6-Cycles into a Linear Forest and a Forest[J]. Graphs and Combinatorics, 2023, 39(1): 10-1-10-12.

[15] Wang Y, Wang J L, Wang W F, et al. Partitioning Planar Graphs into Bounded Degree Forests[J]. Applied Mathematics and Computation, 2024, 474: 128705-1-128705-8.

[16] Hu K Y, Huang M F. An ($\mathscr{F}_{3}$,$\mathscr{F}_{4}$)-Partition of Planar Graphs without 4- and 6-Cycles[J]. Discrete Applied Mathematics, 2025, 373: 1-9.

基金资助

国家自然科学基金(12261094)