Acyclic Edge Coloring of Chordal Graphs with Bounded Degree

被引：2
作者：
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
    Abu-Khzam, Faisal N.
    Heggernes, Pinar
    [J]. INFORMATION PROCESSING LETTERS, 2016, 116 (12) : 739 - 743
  • [2] Acyclic edge colorings of graphs
    Alon, N
    Sudakov, B
    Zaks, A
    [J]. JOURNAL OF GRAPH THEORY, 2001, 37 (03) : 157 - 167
  • [3] ACYCLIC COLORING OF GRAPHS
    ALON, N
    MCDIARMID, C
    REED, B
    [J]. RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (03) : 277 - 288
  • [4] Acyclic edge coloring of subcubic graphs
    Basavaraju, Manu
    Chandran, L. Sunil
    [J]. DISCRETE MATHEMATICS, 2008, 308 (24) : 6650 - 6653
  • [5] ACYCLIC EDGE-COLORING OF PLANAR GRAPHS
    Basavaraju, Manu
    Chandran, L. Sunil
    Cohen, Nathann
    Havet, Frederic
    Mueller, Tobias
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) : 463 - 478
  • [6] Acyclic edge coloring of 2-degenerate graphs
    Basavaraju, Manu
    Chandran, L. Sunil
    [J]. JOURNAL OF GRAPH THEORY, 2012, 69 (01) : 1 - 27
  • [7] Acyclic Edge Coloring of Graphs with Maximum Degree 4
    Basavaraju, Manu
    Chandran, L. Sunill
    [J]. JOURNAL OF GRAPH THEORY, 2009, 61 (03) : 192 - 209
  • [8] Acyclic edge-coloring using entropy compression
    Esperet, Louis
    Parreau, Aline
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (06) : 1019 - 1027
  • [9] Fiamcik J., 1978, Math Slovaca, V28, P139
  • [10] Acyclic edge coloring through the Lovasz Local Lemma
    Giotis, Ioannis
    Kirousis, Lefteris
    Psaromiligkos, Kostas I.
    Thilikos, Dimitrios M.
    [J]. THEORETICAL COMPUTER SCIENCE, 2017, 665 : 40 - 50
12