A Brooks type theorem for the maximum local edge connectivity (Q1753016): Difference between revisions
From MaRDI portal
Latest revision as of 16:33, 15 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A Brooks type theorem for the maximum local edge connectivity |
scientific article |
Statements
A Brooks type theorem for the maximum local edge connectivity (English)
0 references
25 May 2018
0 references
Summary: 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 \textit{P. Aboulker} et al. [J. Graph Theory 85, No. 4, 814--838 (2017; Zbl 1368.05040)]. 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.
0 references
graph coloring
0 references
connectivity
0 references
critical graphs
0 references
Brooks' theorem
0 references