A Brooks type theorem for the maximum local edge connectivity

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Brooks' theorem connectivity critical graphs graph coloring

Coloring of graphs and hypergraphs (05C15)

Abstract: For a graph

G

, let

c n (G)

and

l a (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

c n (G) l e q l a (G) + 1

. In this paper we characterize the graphs

G

for which

c n (G) = l a (G) + 1

. The case

l a (G) = 3

was already solved by Alboulker {em et al.,} cite{AlboukerV2016}. We show that a graph

G

with

l a (G) = k g e q 4

satisfies

c n (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.

Review text

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.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: A Brooks type theorem for the maximum local edge connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1753016)