The list chromatic index of simple graphs whose odd cycles intersect in at most one edge

被引:1
作者
McDonald, Jessica [1 ]
Puleo, Gregory J. [1 ]
机构
[1] Auburn Univ, Dept Math & Stat, Auburn, AL 36849 USA
关键词
Edge list coloring; Kernel-perfect orientation; Line graph; 2-connected; Chromatic index; Odd cycles; LINE-GRAPHS; CHOOSABILITY;
D O I
10.1016/j.disc.2017.11.012
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We study the class of simple graphs g* for which every pair of distinct odd cycles intersect in at most one edge. We give a structural characterization of the graphs in g* and prove that every G is an element of g* satisfies the list-edge-coloring conjecture. When Delta(G) >= 4, we in fact prove a stronger result about kernel-perfect orientations in L(G) which implies that G is (m Delta(G) : m)-edge-choosable and Delta(G)-edge-paintable for every m >= 1. (C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码:713 / 722
页数:10
相关论文
共 16 条
  • [1] A STRENGTHENING ON ODD CYCLES IN GRAPHS OF GIVEN CHROMATIC NUMBER
    Gao, Jun
    Huo, Qingyi
    Ma, Jie
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (04) : 2317 - 2327
  • [2] Characterization of graphs whose signature equals the number of odd cycles
    Ma, Xiaobin
    Wong, Dein
    Tian, Fenglei
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 511 : 259 - 273
  • [3] Strong list-chromatic index of subcubic graphs
    Dai, Tianjiao
    Wang, Guanghui
    Yang, Donglei
    Yu, Gexin
    DISCRETE MATHEMATICS, 2018, 341 (12) : 3434 - 3440
  • [4] Edge-disjoint odd cycles in planar graphs
    Král, D
    Voss, HJ
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 90 (01) : 107 - 120
  • [5] Tight bounds on the chromatic edge stability index of graphs
    Akbari, Saieed
    Haslegrave, John
    Javadi, Mehrbod
    Nahvi, Nasim
    Niaparast, Helia
    DISCRETE MATHEMATICS, 2024, 347 (04)
  • [6] List edge and list total colorings of planar graphs without short cycles
    Liu, Bin
    Hou, Jianfeng
    Liu, Guizhen
    INFORMATION PROCESSING LETTERS, 2008, 108 (06) : 347 - 351
  • [7] Edge-disjoint odd cycles in 4-edge-connected graphs
    Kawarabayashi, Ken-ichi
    Kobayashi, Yusuke
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 119 : 12 - 27
  • [8] Edge-disjoint Odd Cycles in 4-edge-connected Graphs
    Kawarabayashi, Ken-ichi
    Kobayashi, Yusuke
    29TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, (STACS 2012), 2012, 14 : 206 - 217
  • [9] LIST EDGE AND LIST TOTAL COLORINGS OF PLANAR GRAPHS WITHOUT 6-CYCLES WITH CHORD
    Dong, Aijun
    Liu, Guizhen
    Li, Guojun
    BULLETIN OF THE KOREAN MATHEMATICAL SOCIETY, 2012, 49 (02) : 359 - 365
  • [10] The Chromatic Index of Proper Circular-arc Graphs of Odd Maximum Degree which are Chordal
    Bernardi, Joao Pedro W.
    da Silva, Murilo V. G.
    Guedes, Andre Luiz P.
    Zatesko, Leandro M.
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 : 125 - 133