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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom