A note of vertex arboricity of planar graphs without 4-cycles intersecting with 6-cycles

被引：10

作者：

Cui, Xuyang ^{[1
]}

Teng, Wenshun ^{[1
]}

Liu, Xing ^{[1
]}

Wang, Huijuan ^{[1
]}

机构：

[1] Qingdao Univ, Sch Math & Stat, Qingdao 266071, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2020年 / 836卷

关键词：

Intersecting; Planar graphs; Vertex arboricity; POINT-ARBORICITY;

D O I：

10.1016/j.tcs.2020.06.009

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The vertex arboricity va(G) of G is the smallest integer k which the acyclic partition of V (G) make the vertex set V (G) be partitioned into k subsets which each subset induces an acyclic graph. In this paper, we mainly study vertex arboricity of planar graphs, and we prove that if there is without 4-cycles intersecting with 6-cycles, then va(G) <= 2 (C) 2020 Elsevier B.V. All rights reserved.

引用

页码：53 / 58

页数：6

共 13 条

[1]

[Anonymous], 2019, IEEE ACCESS, DOI DOI 10.1109/ACCESS.2019.2924052

[2]

Bickle A., 2019, AKCE INT J GRAPHS CO

[3]

Cai H., 2017, J COMB OPTIM, V35, P365

[4] POINT-ARBORICITY OF A GRAPH [J].

CHARTRAND, G ;

KRONK, HV ;

WALL, CE .

ISRAEL JOURNAL OF MATHEMATICS, 1968, 6 (02) :169-+

[5] POINT-ARBORICITY OF PLANAR GRAPHS [J].

CHARTRAND, G ;

KRONK, HV .

JOURNAL OF THE LONDON MATHEMATICAL SOCIETY, 1969, 44 (176P) :612-+

[6] Vertex-arboricity of planar graphs without intersecting triangles [J].

Chen, Min ;

Raspaud, Andre ;

Wang, Weifan .

EUROPEAN JOURNAL OF COMBINATORICS, 2012, 33 (05) :905-923

[7]

Choi I., 2013, J DISCRETE MATH, V333, P101

[8] Vertex arboricity of planar graphs without chordal 6-cycles [J].

Huang, Danjun ;

Wang, Weifan .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2013, 90 (02) :258-272

[9] On the vertex-arboricity of planar graphs without 7-cycles [J].

Huang, Danjun ;

Shiu, Wai Chee ;

Wang, Weifan .

DISCRETE MATHEMATICS, 2012, 312 (15) :2304-2315

[10] On the vertex-arboricity of K5-minor-free graphs of diameter 2 [J].

Huang, Fei ;

Wang, Xiumei ;

Yuan, Jinjiang .

DISCRETE MATHEMATICS, 2014, 322 :1-4

← 1 2 →