A Brooks type theorem for the maximum local edge connectivity

Publikation: Forskning - peer reviewTidsskriftartikel

Dokumenter

Links

Vis graf over relationer

For a graph $G$, let $\cn(G)$ and $\la(G)$ denote the chromatic number of $G$ and the maximum local edge connectivity of $G$, respectively. A result of Dirac \cite{Dirac53} implies that every graph $G$ satisfies $\cn(G)\leq \la(G)+1$. In this paper we characterize the graphs $G$ for which $\cn(G)=\la(G)+1$. The case $\la(G)=3$ was already solved by Alboulker {\em et al.\,} \cite{AlboukerV2016}. We show that a graph $G$ with $\la(G)=k\geq 4$ satisfies $\cn(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\'os join.
OriginalsprogEngelsk
TidsskriftThe Electronic Journal of Combinatorics
ISSN1077-8926
StatusAfsendt - 2017

Bibliografisk note

15 pages, 1 figure