Coloring hypergraphs of low connectivity

Abstract: For a hypergraph

G

, let

c h i (G), D e l t a (G),

and

l a m b d a (G)

denote the chromatic number, the maximum degree, and the maximum local edge connectivity of

G

, respectively. A result of Rhys Price Jones from 1975 says that every connected hypergraph

G

satisfies

c h i (G) l e q D e l t a (G) + 1

and equality holds if and only if

G

is a complete graph, an odd cycle, or

G

has just one (hyper-)edge. By a result of Bjarne Toft from 1970 it follows that every hypergraph

G

satisfies

c h i (G) l e q l a m b d a (G) + 1

. In this paper, we show that a hypergraph

G

with

l a m b d a (G) g e q 3

satisfies

c h i (G) = l a m b d a (G) + 1

if and only if

G

contains a block which belongs to a family

m a t h c a l H_{l a m b d a (G)}

. The class

m a t h c a l H_{3}

is the smallest family which contains all odd wheels and is closed under taking Haj'os joins. For

k g e q 4

, the family

m a t h c a l H_{k}

is the smallest that contains all complete graphs

K_{k + 1}

and is closed under Haj'os joins. For the proofs of the above results we use critical hypergraphs. A hypergraph

G

is called

(k + 1)

-critical if

c h i (G) = k + 1

, but

c h i (H) l e q k

whenever

H

is a proper subhypergraph of

G

. We give a characterization of

(k + 1)

-critical hypergraphs having a separating edge set of size

k

as well as a a characterization of

(k + 1)

-critical hypergraphs having a separating vertex set of size

2

.

Recommendations

Cited in

(5)

This page was built for publication: Coloring hypergraphs of low connectivity