Forcing clique immersions through chromatic number

Preprint English OPEN
Gauthier, Gregory; Le, Tien-Nam; Wollan, Paul;
  • Subject: Mathematics - Combinatorics

Building on recent work of Dvo\v{r}\'ak and Yepremyan, we show that every simple graph of minimum degree $7t+7$ contains $K_t$ as an immersion and that every graph with chromatic number at least $3.54t + 4$ contains $K_t$ as an immersion. We also show that every graph o... View more
  • References (17)
    17 references, page 1 of 2

    [1] F. Abu-Khzam and M. Langston, Graph coloring and the immersion order, Lecture Notes in Computer Science 2697 (2003), 394-403.

    [2] M. Devos, Z. Dvoˇra´k, J. Fox, J. McDonald, B. Mohar, and D. Scheide, Minimum degree condition forcing complete graph immersion, Combinatorica 34 (2014), 279- 298.

    [3] Z. Dvoˇra´k and L. Yepremyan, Comptete graph immersions and minimum degree, preprint, arXiv:1512.00513.

    [4] M. Devos, K. Kawarabayashi, B. Mohar, and H. Okamura, Immersing small complete graphs, Ars Math. Contemp. 3 (2010), 139-146.

    [5] P. Duchet and H. Meyniel, On Hadwigers number and the stability number, Ann. Discrete Math. 13 (1982), 71-74.

    [6] J. Fox and F. Wei, On the number of cliques in graphs with a forbidden subdivision or immersion, preprint, arXiv:1606.06810.

    [7] H. Hadwiger, Uber eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zurich 88 (1943), 133-143.

    [8] A. Kostochka, Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica 4 (1984), 307-316.

    [9] T.-N. Le and P. Wollan, Forcing clique immersions through chromatic number, Electronic Notes Disc. Math. 54(1) (2016), 121-126.

    [10] F. Lescure and H. Meynial, On a problem upon configurations contained in graphs with given chromatic number, Ann. Discrete Math. 41 (1989), 325-331. Graph theory in memory of G.A. Dirac, Sandbjerg (1985).

  • Related Organizations (6)
  • Metrics
Share - Bookmark