Path partition of planar graphs with girth at least six

被引:0
作者
Liu, Xiaoling [1 ]
Sun, Lei [1 ]
Zheng, Wei [1 ]
机构
[1] Shandong Normal Univ, Sch Math & Stat, Jinan 250014, Peoples R China
基金
中国国家自然科学基金;
关键词
Planar graph; path partition; girth; discharging; FORESTS; MAP;
D O I
10.1142/S1793830922501580
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A graph G has a (P-k1,P-k2)-partition if V(G) can be partitioned into two nonempty disjoint subsets V-1 and V-2 so that G[V-1] and G[V-2] are graphs whose components are paths of order at most k(1) and k(2), respectively. In this paper, we proved that every planar graph with girth at least six giving that i-cycle is not intersecting with j-cycle admits a (P-3, P-3)-partition, where i is an element of {6, 7} and j is an element of {6, 7, 8, 9).
引用
收藏
页数:7
相关论文
共 12 条
[1]   Partitioning into graphs with only small components [J].
Alon, N ;
Ding, GL ;
Oporowski, B ;
Vertigan, D .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 87 (02) :231-243
[2]   EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING [J].
APPEL, K ;
HAKEN, W .
ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :429-490
[3]   EVERY PLANAR MAP IS 4 COLORABLE .2. REDUCIBILITY [J].
APPEL, K ;
HAKEN, W ;
KOCH, J .
ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :491-567
[4]   Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths [J].
Axenovich, Maria ;
Ueckerdt, Torsten ;
Weiner, Pascal .
JOURNAL OF GRAPH THEORY, 2017, 85 (03) :601-618
[5]   On 1-improper 2-coloring of sparse graphs [J].
Borodin, O. V. ;
Kostochka, A. ;
Yancey, M. .
DISCRETE MATHEMATICS, 2013, 313 (22) :2638-2649
[6]   List Strong Linear 2-Arboricity of Sparse Graphs [J].
Borodin, Oleg V. ;
Ivanova, Anna O. .
JOURNAL OF GRAPH THEORY, 2011, 67 (02) :83-90
[7]   Partitioning sparse graphs into an independent set and a graph with bounded size components [J].
Choi, Ilkyoo ;
Dross, Francois ;
Ochem, Pascal .
DISCRETE MATHEMATICS, 2020, 343 (08)
[8]   ACYCLIC COLORINGS OF PLANAR GRAPHS [J].
GODDARD, W .
DISCRETE MATHEMATICS, 1991, 91 (01) :91-94
[9]  
Montassier M, 2015, ELECTRON J COMB, V22
[10]   ON THE LINEAR VERTEX-ARBORICITY OF A PLANAR GRAPH [J].
POH, KS .
JOURNAL OF GRAPH THEORY, 1990, 14 (01) :73-75