Acyclic coloring of claw-free graphs with small degree

被引：1

作者：

Wang, Juan ^{[1
]}

Liang, Zuosong ^{[1
,2
]}

Cai, Jiansheng ^{[3
]}

Miao, Lianying ^{[4
]}

机构：

[1] Qufu Normal Univ, Sch Management, Rizhao 276826, Peoples R China

[2] Guangxi Minzu Univ, Coll Math & Phys, Nanning 530006, Peoples R China

[3] Weifang Univ, Sch Math & Informat Sci, Weifang 261061, Peoples R China

[4] China Univ Min & Technol, Sch Math, Xuzhou 221116, Jiangsu, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2022年 / 321卷

基金：

中国国家自然科学基金;

关键词：

Vertex coloring; Acyclic coloring; Claw-free graph; MAXIMUM DEGREE;

D O I：

10.1016/j.dam.2022.07.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

An acyclic k-coloring of a graph is a proper vertex coloring using k colors such that every cycle is colored with at least three colors. A graph is claw-free if it contains no K-1,K-3 as an induced subgraph. Grunbaum (1973) conjectured that every graph with maximum degree Delta has an acyclic (Delta + 1)-coloring. In this paper, we show that this conjecture holds for the claw-free graphs with Delta <= 6. (c) 2022 Elsevier B.V. All rights reserved.

引用

页码：272 / 280

页数：9

共 18 条

[1] ACYCLIC COLORING OF GRAPHS [J].

ALON, N ;

MCDIARMID, C ;

REED, B .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (03) :277-288

[2] ACYCLIC COLORINGS OF PLANAR GRAPHS [J].

BORODIN, OV .

DISCRETE MATHEMATICS, 1979, 25 (03) :211-236

[3]

Burstein M.I., 1979, SOOBSHCH AKAD NAUK G, V93, P21

[4]

Cai J., 2019, RESTRICTED COLOIRNGS

[5] Improved Upper Bound for Generalized Acyclic Chromatic Number of Graphs [J].

Cai, Jian-sheng ;

Zhu, Xu-ding .

ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2018, 34 (04) :798-800

[6] Acyclic coloring of graphs of maximum degree five: Nine colors are enough [J].

Fertin, Guillaume ;

Raspaud, Andre .

INFORMATION PROCESSING LETTERS, 2007, 105 (02) :65-72

[7] Acyclic colorings of graphs with bounded degree [J].

Fiedorowicz, Anna ;

Sidorowicz, Elizbieta .

SCIENCE CHINA-MATHEMATICS, 2016, 59 (07) :1427-1440

[8] ACYCLIC 6-COLOURING OF GRAPHS WITH MAXIMUM DEGREE 5 AND SMALL MAXIMUM AVERAGE DEGREE [J].

Fiedorowicz, Anna .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (01) :91-99

[9] ACYCLIC COLORINGS OF PLANAR GRAPHS [J].

GRUNBAUM, B .

ISRAEL JOURNAL OF MATHEMATICS, 1973, 14 (04) :390-408

[10] Graphs with maximum degree 6 are acyclically 11-colorable [J].

Hocquard, Herve .

INFORMATION PROCESSING LETTERS, 2011, 111 (15) :748-753

← 1 2 →