1Technical Universität Ilmenau Institute of Mathematics PF 100565 D-98684 Ilmenau Germany 2University of Southern Denmark IMADA Campusvej 55 DK-5320 Odense M Denmark
The electronic journal of combinatorics, Tome 25 (2018) no. 1
For a graph $G$, let $\chi(G)$ and $\lambda(G)$ denote the chromatic number of $G$ and the maximum local edge connectivity of $G$, respectively. A result of Dirac implies that every graph $G$ satisfies $\chi(G)\leq \lambda(G)+1$. In this paper we characterize the graphs $G$ for which $\chi(G)=\lambda(G)+1$. The case $\lambda(G)=3$ was already solved by Aboulker, Brettell, Havet, Marx, and Trotignon. We show that a graph $G$ with $\lambda(G)=k\geq 4$ satisfies $\chi(G)=k+1$ if and only if $G$ contains a block which can be obtained from copies of $K_{k+1}$ by repeated applications of the Hajós join.
1
Technical Universität Ilmenau
Institute of Mathematics
PF 100565
D-98684 Ilmenau
Germany
2
University of Southern Denmark
IMADA
Campusvej 55
DK-5320 Odense M
Denmark
@article{10_37236_6043,
author = {Michael Stiebitz and Bjarne Toft},
title = {A {Brooks} type theorem for the maximum local edge connectivity},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {1},
doi = {10.37236/6043},
zbl = {1392.05043},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6043/}
}
TY - JOUR
AU - Michael Stiebitz
AU - Bjarne Toft
TI - A Brooks type theorem for the maximum local edge connectivity
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/6043/
DO - 10.37236/6043
ID - 10_37236_6043
ER -
%0 Journal Article
%A Michael Stiebitz
%A Bjarne Toft
%T A Brooks type theorem for the maximum local edge connectivity
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/6043/
%R 10.37236/6043
%F 10_37236_6043
Michael Stiebitz; Bjarne Toft. A Brooks type theorem for the maximum local edge connectivity. The electronic journal of combinatorics, Tome 25 (2018) no. 1. doi: 10.37236/6043
