Building on recent work of Dvořák 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 on n vertices with no independent set of size three contains K 2⌊n∕5⌋ as an immersion.
Forcing clique immersions through chromatic number / Gauthier, G.; Le, T. -N.; Wollan, P.. - In: EUROPEAN JOURNAL OF COMBINATORICS. - ISSN 0195-6698. - 81:(2019), pp. 98-118. [10.1016/j.ejc.2019.04.003]
Forcing clique immersions through chromatic number
Gauthier G.;Wollan P.
2019
Abstract
Building on recent work of Dvořák 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 on n vertices with no independent set of size three contains K 2⌊n∕5⌋ as an immersion.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
