We conjecture that any graph $G$ with treewidth $k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. We also show that any graph $G$ with treewidth $k\geq 4$ and maximum degree $2k-1$ satisfies $\chi'(G)=\Delta(G)$, extending an old result of Vizing.
@article{10_37236_6042,
author = {Henning Bruhn and Laura Gellert and Richard Lang},
title = {Chromatic index, treewidth and maximum degree},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {2},
doi = {10.37236/6042},
zbl = {1391.05102},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6042/}
}
TY - JOUR
AU - Henning Bruhn
AU - Laura Gellert
AU - Richard Lang
TI - Chromatic index, treewidth and maximum degree
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/6042/
DO - 10.37236/6042
ID - 10_37236_6042
ER -
%0 Journal Article
%A Henning Bruhn
%A Laura Gellert
%A Richard Lang
%T Chromatic index, treewidth and maximum degree
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/6042/
%R 10.37236/6042
%F 10_37236_6042
Henning Bruhn; Laura Gellert; Richard Lang. Chromatic index, treewidth and maximum degree. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/6042
