Planar graphs without 4-, 7-, 9-cycles and 5-cycles normally adjacent to 3-cycles

被引：0

作者：

Liu, Zhengjiao ^{[1
]}

Wang, Tao ^{[2
]}

Yang, Xiaojing ^{[1
]}

机构：

[1] Henan Univ, Sch Math & Stat, Kaifeng 475004, Peoples R China

[2] Henan Univ, Ctr Appl Math, Kaifeng 475004, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2024年 / 358卷

基金：

中国国家自然科学基金;

关键词：

Planar graph; (I; F)-partition; Weak degeneracy; Transversal;

D O I：

10.1016/j.dam.2024.07.003

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A graph is (I,F)-partitionableif its vertex set can be partitioned into two parts suchthat one partIis an independent set, and the otherFinduces a forest. A graphisk-degenerateif every subgraphHcontains a vertex of degree at mostkinH.Bernshteyn and Lee defined a generalization ofk-degenerate graphs, which is calledweakly k-degenerate. In this paper, we show that planar graphs without 4-, 7-, 9-cycles,and 5-cycles normally adjacent to 3-cycles are both (I,F)-partitionable and weakly2-degenerate. (c) 2024ElsevierB.V.Allrightsarereserved,includingthosefortextanddatamining,AItraining,andsimilartechnologies.

引用

页码：158 / 166

页数：9

共 50 条

[21] 2-DISTANCE COLORING OF PLANAR GRAPHS WITHOUT 4-CYCLES AND 5-CYCLES [J].

Dong, Wei ;

Xu, Baogang .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (03) :1297-1312

[22] 2-Distance coloring of planar graphs without adjacent 5-cycles [J].

Bu, Yuehua ;

Zhang, Zewei ;

Zhu, Hongguo .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2023, 45 (05)

[23] List-Coloring the Squares of Planar Graphs without 4-Cycles and 5-Cycles [J].

Cranston, Daniel W. ;

Jaeger, Bobby .

JOURNAL OF GRAPH THEORY, 2017, 85 (04) :721-737

[24] Planar graphs with distance of 3-cycles at least 2 and no cycles of lengths 5, 6, 7 [J].

Wang, Tao ;

Wang, Ya-Nan ;

Yang, Xiaojing .

APPLIED MATHEMATICS AND COMPUTATION, 2024, 481

[25] Total colorings of planar graphs without intersecting 4-cycles and intersecting 5-cycles [J].

Tan, Xiang ;

Chen, Hong-Yu .

UTILITAS MATHEMATICA, 2017, 104 :141-150

[26] Acyclic 4-Choosability of Planar Graphs with No 4- and 5-Cycles [J].

Borodin, Oleg V. ;

Ivanova, Anna O. .

JOURNAL OF GRAPH THEORY, 2013, 72 (04) :374-397

[27] Adjacent vertex distinguishing edge coloring of planar graphs without 3-cycles [J].

Huang, Danjun ;

Zhang, Xiaoxiu ;

Wang, Weifan ;

Finbow, Stephen .

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (04)

[28] Planar graphs without intersecting 5-cycles are 4-choosable [J].

Hu, Dai-Qiang ;

Wu, Jian-Liang .

DISCRETE MATHEMATICS, 2017, 340 (08) :1788-1792

[29] Linear 2-Arboricity of Planar Graphs with Neither 3-Cycles Nor Adjacent 4-Cycles [J].

Hong-Xia Niu ;

Jian-Sheng Cai .

Graphs and Combinatorics, 2013, 29 :661-667

[30] Partitioning planar graphs without 4-cycles and 5-cycles into two forests with a specific condition [J].

Tangjai, Wipawee ;

Nakprasit, Kittikorn ;

Nakprasit, Keaitsuda Maneeruk ;

Sittitrai, Pongpat .

DISCRETE APPLIED MATHEMATICS, 2024, 342 :347-354

← 1 2 3 4 5 →