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.
机构:
Shandong Univ, Dept Math, Jinan, Shandong, Peoples R ChinaShandong Univ, Dept Math, Jinan, Shandong, Peoples R China
Dai, Tianjiao
Wang, Guanghui
论文数: 0引用数: 0
h-index: 0
机构:
Shandong Univ, Dept Math, Jinan, Shandong, Peoples R ChinaShandong Univ, Dept Math, Jinan, Shandong, Peoples R China
Wang, Guanghui
Yang, Donglei
论文数: 0引用数: 0
h-index: 0
机构:
Shandong Univ, Dept Math, Jinan, Shandong, Peoples R ChinaShandong Univ, Dept Math, Jinan, Shandong, Peoples R China
Yang, Donglei
Yu, Gexin
论文数: 0引用数: 0
h-index: 0
机构:
Coll William & Mary, Dept Math, Williamsburg, VA 23185 USA
Cent China Normal Univ, Dept Math, Wuhan, Hubei, Peoples R ChinaShandong Univ, Dept Math, Jinan, Shandong, Peoples R China
机构:
Res Org Informat & Syst, Natl Inst Informat, Chiyoda Ku, 2-1-2 Hitotsubashi, Tokyo 1018430, JapanRes Org Informat & Syst, Natl Inst Informat, Chiyoda Ku, 2-1-2 Hitotsubashi, Tokyo 1018430, Japan
Kawarabayashi, Ken-ichi
Kobayashi, Yusuke
论文数: 0引用数: 0
h-index: 0
机构:
Univ Tokyo, Tokyo 1138656, JapanRes Org Informat & Syst, Natl Inst Informat, Chiyoda Ku, 2-1-2 Hitotsubashi, Tokyo 1018430, Japan