×

Forcing clique immersions through chromatic number. (English) Zbl 1420.05057

Summary: Building on recent work of Z. Dvořák and L. Yepremyan [J. Graph Theory 88, No. 1, 211–221 (2018; Zbl 1391.05084)], we show that every simple graph of minimum degree \(7 t + 7\) contains \(K_t\) as an immersion and that every graph with chromatic number at least \(3 . 54 t + 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 \lfloor n / 5 \rfloor}\) as an immersion.

MSC:

05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory

Citations:

Zbl 1391.05084
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abu-Khzam, F.; Langston, M., Graph coloring and the immersion order, Lecture Notes in Comput. Sci., 2697, 394-403 (2003) · Zbl 1276.05042
[2] Devos, M.; Dvořák, Z.; Fox, J.; McDonald, J.; Mohar, B.; Scheide, D., Minimum degree condition forcing complete graph immersion, Combinatorica, 34, 279-298 (2014) · Zbl 1349.05180
[3] Devos, M.; Kawarabayashi, K.; Mohar, B.; Okamura, H., Immersing small complete graphs, Ars Math. Contemp., 3, 139-146 (2010) · Zbl 1213.05137
[4] Duchet, P.; Meyniel, H., On Hadwiger’s number and the stability number, Annal Discret. Math., 13, 71-74 (1982) · Zbl 0522.05060
[5] Dvořák, Z.; Yepremyan, L., Comptete graph immersions and minimum degree, J. Graph Theory, 88, 211-221 (2018) · Zbl 1391.05084
[6] J. Fox, F. Wei, On the number of cliques in graphs with a forbidden subdivision or immersion, preprint, https://arxiv.org/abs/1606.06810; J. Fox, F. Wei, On the number of cliques in graphs with a forbidden subdivision or immersion, preprint, https://arxiv.org/abs/1606.06810
[7] Hadwiger, H., Uber eine klassifikation der streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zurich, 88, 133-143 (1943) · Zbl 0061.41308
[8] Kostochka, A., Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica, 4, 307-316 (1984) · Zbl 0555.05030
[9] Le, T.-N.; Wollan, P., Forcing clique immersions through chromatic number, Electron. Notes Discrete Math., 54, 1, 121-126 (2016) · Zbl 1356.05052
[10] Lescure, F.; Meyniel, H., On a problem upon configurations contained in graphs with given chromatic number, Annal Discret. Math., 41, 325-331 (1989), Graph theory in memory of G.A. Dirac, Sandbjerg (1985) · Zbl 0675.05026
[11] Plummer, M. D.; Stiebitz, M.; Toft, B., On a special case of Hadwiger’s conjecture, Discuss. Math. Graph Theory, 23, 333-363 (2005) · Zbl 1053.05052
[12] Robertson, N.; Seymour, P. D., Graph minors XXIII, Nash-Williams’ immersion conjecture, J. Combin. Theory Ser. B, 100, 181-205 (2010) · Zbl 1216.05151
[13] Robertson, N.; Seymour, P. D.; Thomas, R., Hadwiger’s conjecture for K6-free graphs, Combinatorica, 13, 279-361 (1993) · Zbl 0830.05028
[14] Thomason, A., An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc., 95, 261-265 (1984) · Zbl 0551.05047
[15] Vergara, S., Complete graph immersions in dense graphs, Discret. Math., 340, 5, 1019-1027 (2017) · Zbl 1357.05072
[16] Wagner, K., Über eine eigenschaft der ebenen komplexe, Math. Ann., 114, 570-590 (1937) · JFM 63.0550.01
[17] Wollan, P., The structure of graphs not admitting a fixed immersion, J. Combin. Theory Ser. B, 110, 47-66 (2015) · Zbl 1302.05148
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.