2016/03/30 by Stiebitz, Michael, Toft, Bjarne
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1603.09187
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 \citeDirac53 implies that every graph G satisfies \cn(G)≤ \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. \citeAlboukerV2016. We show that a graph G with \la(G)=k≥ 4 satisfies \cn(G)=k+1 if and only if G contains a block which can be obtained from copies of Kk+1 by repeated applications of the Hajós join.