A Brooks type theorem for the maximum local edge connectivity

Michael Stiebitz, Bjarne Toft

Research output: Contribution to journalJournal articleResearchpeer-review

46 Downloads (Pure)


For a graph G, let χ(G) and λ(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 χ(G) 6 λ(G) + 1. In this paper we characterize the graphs G for which χ(G) = λ(G) + 1. The case λ(G) = 3 was already solved by Aboulker, Brettell, Havet, Marx, and Trotignon. We show that a graph G with λ(G) = k > 4 satisfies χ(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.

Original languageEnglish
Article number#P1.50
JournalThe Electronic Journal of Combinatorics
Issue number1
Number of pages11
Publication statusPublished - 2018



  • math.CO
  • Graph coloring
  • Connectivity
  • Critical graphs
  • Brooks’ theorem

Cite this