Partitioning Planar Graphs without 4-Cycles and 6-Cycles into a Linear Forest and a Forest

被引：2

作者：

Huang, Xiaojie ^{[1
]}

Huang, Ziwen ^{[1
]}

Lv, Jian-Bo ^{[2
]}

机构：

[1] Yichun Univ, Ctr Appl Math, Sch Math & Comp Sci, Yichun 336000, Jiangxi, Peoples R China

[2] Guangxi Normal Univ, Dept Math, Guilin 541000, Peoples R China

来源：

GRAPHS AND COMBINATORICS | 2023年 / 39卷 / 01期

基金：

中国国家自然科学基金;

关键词：

Planar graph; Partition; Forest; F-2-saturated; DEFECTIVE; 2-COLORINGS; MAP;

D O I：

10.1007/s00373-022-02605-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G = (V(G), E(G)) be a graph and G(i) be a class of graphs for each i is an element of [k]. A (G(1), . . . , G(k))-partition of G is a partition of V (G) into k sets V-1, ... , V-k such that, for each j is an element of [k], the graph G[V-j] induced by V-j is a graph in G(j). In this paper, we prove that every planar graph without 4-cycles and 6-cycles admits an (F-2, F)-partition. As a corollary, V (G) can be partitioned into two sets V-1 and V-2 such that V-1 induces a linear forest and V-2 induces a forest if G is a planar graph without 4-cycles and 6-cycles.

引用

页数：12

共 50 条

[1] Partitioning Planar Graphs without 4-Cycles and 6-Cycles into a Linear Forest and a Forest
Xiaojie Huang
Ziwen Huang
Jian-Bo Lv
Graphs and Combinatorics, 2023, 39
[2] A Weak DP-Partitioning of Planar Graphs without 4-Cycles and 6-Cycles
Sittitrai, Pongpat
Nakprasit, Keaitsuda Maneeruk
Nakprasit, Kittikorn
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2023, 46 (04)
[3] Vertex 2-arboricity of planar graphs without 4-cycles adjacent to 6-cycles
Nakprasit, Kittikorn
Ruksasakchai, Watcharintorn
Sittitrai, Pongpat
THEORETICAL COMPUTER SCIENCE, 2023, 941 : 131 - 139
[4] Vertex 2-arboricity of planar graphs without 4-cycles adjacent to 6-cycles
Nakprasit, Kittikorn
Ruksasakchai, Watcharintorn
Sittitrai, Pongpat
THEORETICAL COMPUTER SCIENCE, 2023, 941 : 131 - 139
[5] Every planar graph without 4-cycles and 6-cycles is (2,9)-colorable
Ma, Jianqing
Huang, Mingfang
Zhang, Xiaoxia
ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2022, (48): : 659 - 670
[6] Partitioning planar graphs without 4-cycles and 5-cycles into two forests with a specific condition
Tangjai, Wipawee
Nakprasit, Kittikorn
Nakprasit, Keaitsuda Maneeruk
Sittitrai, Pongpat
DISCRETE APPLIED MATHEMATICS, 2024, 342 : 347 - 354
[7] Linear Coloring of Planar Graphs Without 4-Cycles
Wang, Weifan
Wang, Yiqiao
GRAPHS AND COMBINATORICS, 2013, 29 (04) : 1113 - 1124
[8] The Linear Arboricity of Planar Graphs without 5-cycles and 6-cycles
Tan, Xiang
Chen, Hong-Yu
Wu, Jian-Liang
ARS COMBINATORIA, 2010, 97A : 367 - 375
[9] Linear Coloring of Planar Graphs Without 4-Cycles
Weifan Wang
Yiqiao Wang
Graphs and Combinatorics, 2013, 29 : 1113 - 1124
[10] Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
Cho, Eun-Kyung
Choi, Ilkyoo
Park, Boram
DISCRETE MATHEMATICS, 2021, 344 (01)

← 1 2 3 4 5 →