Acyclic Edge Coloring of Chordal Graphs with Bounded Degree

被引：3

作者：

Ma, Yulai ^{[1
,2
]}

Shi, Yongtang ^{[1
,2
]}

Wang, Weifan ^{[3
]}

机构：

[1] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China

[2] Nankai Univ, LPMC, Tianjin 300071, Peoples R China

[3] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China

来源：

GRAPHS AND COMBINATORICS | 2021年 / 37卷 / 06期

基金：

中国国家自然科学基金;

关键词：

Acyclic edge coloring; Chordal graphs; Simplicial vertices; Maximum degree; 4-REGULAR GRAPHS;

D O I：

10.1007/s00373-021-02378-7

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. It was conjectured that every simple graph G with maximum degree Delta is acyclically edge-(Delta + 2)-colorable. In this paper, we confirm the conjecture for chordal graphs G with Delta <= 6.

引用

页码：2621 / 2636

页数：16

共 17 条

[1] Enumerating minimal dominating sets in chordal graphs [J].

Abu-Khzam, Faisal N. ;

Heggernes, Pinar .

INFORMATION PROCESSING LETTERS, 2016, 116 (12) :739-743

[2] Acyclic edge colorings of graphs [J].

Alon, N ;

Sudakov, B ;

Zaks, A .

JOURNAL OF GRAPH THEORY, 2001, 37 (03) :157-167

[3] ACYCLIC COLORING OF GRAPHS [J].

ALON, N ;

MCDIARMID, C ;

REED, B .

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

[4] Acyclic edge coloring of subcubic graphs [J].

Basavaraju, Manu ;

Chandran, L. Sunil .

DISCRETE MATHEMATICS, 2008, 308 (24) :6650-6653

[5] ACYCLIC EDGE-COLORING OF PLANAR GRAPHS [J].

Basavaraju, Manu ;

Chandran, L. Sunil ;

Cohen, Nathann ;

Havet, Frederic ;

Mueller, Tobias .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) :463-478

[6] Acyclic edge coloring of 2-degenerate graphs [J].

Basavaraju, Manu ;

Chandran, L. Sunil .

JOURNAL OF GRAPH THEORY, 2012, 69 (01) :1-27

[7] Acyclic Edge Coloring of Graphs with Maximum Degree 4 [J].

Basavaraju, Manu ;

Chandran, L. Sunill .

JOURNAL OF GRAPH THEORY, 2009, 61 (03) :192-209

[8] Acyclic edge-coloring using entropy compression [J].

Esperet, Louis ;

Parreau, Aline .

EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (06) :1019-1027

[9]

Fiamtik I., 1978, MATH SLOVACA, V28, P139

[10] Acyclic edge coloring through the Lovasz Local Lemma [J].

Giotis, Ioannis ;

Kirousis, Lefteris ;

Psaromiligkos, Kostas I. ;

Thilikos, Dimitrios M. .

THEORETICAL COMPUTER SCIENCE, 2017, 665 :40-50

← 1 2 →