Constructing graphs with no immersion of large complete graphs

Abstract: In 1989, Lescure and Meyniel proved, for

d = 5, 6

, that every

d

-chromatic graph contains an immersion of

K_{d}

, and in 2003 Abu-Khzam and Langston conjectured that this holds for all

d

. In 2010, DeVos, Kawarabayashi, Mohar, and Okamura proved this conjecture for

d = 7

. In each proof, the

d

-chromatic assumption was not fully utilized, as the proofs only use the fact that a

d

-critical graph has minimum degree at least

d - 1

. DeVos, Dvov{r}'ak, Fox, McDonald, Mohar, and Scheide show the stronger conjecture that a graph with minimum degree

d - 1

has an immersion of

K_{d}

fails for

d = 10

and

d g e q 12

with a finite number of examples for each value of

d

, and small chromatic number relative to

d

, but it is shown that a minimum degree of

200 d

does guarantee an immersion of

K_{d}

. In this paper we show that the stronger conjecture is false for

d = 8, 9, 11

and give infinite families of examples with minimum degree

d - 1

and chromatic number

d - 3

or

d - 2

that do not contain an immersion of

K_{d}

. Our examples can be up to

(d - 2)

-edge-connected. We show, using Haj'os' Construction, that there is an infinite class of non-

(d - 1)

-colorable graphs that contain an immersion of

K_{d}

. We conclude with some open questions, and the conjecture that a graph

G

with minimum degree

d - 1

and more than

f r a c | V (G) | 1 + m (d + 1)

vertices of degree at least

m d

has an immersion of

K_{d}

.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Constructing graphs with no immersion of large complete graphs