Premium
List Edge‐Coloring and Total Coloring in Graphs of Low Treewidth
Author(s) -
Bruhn Henning,
Lang Richard,
Stein Maya
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21874
Subject(s) - treewidth , combinatorics , mathematics , edge coloring , partial k tree , 1 planar graph , brooks' theorem , total coloring , graph , discrete mathematics , chromatic scale , graph coloring , chordal graph , pathwidth , graph power , line graph
We prove that the list chromatic index of a graph of maximum degree Δ and treewidth ≤ 2 Δ − 3 is Δ; and that the total chromatic number of a graph of maximum degree Δ and treewidth ≤ Δ / 3 + 1 is Δ + 1 . This improves results by Meeks and Scott.