×

Clique immersions in graphs of independence number two with certain forbidden subgraphs. (English) Zbl 1462.05285

Summary: The Lescure-Meyniel conjecture is the analogue of Hadwiger’s conjecture for the immersion order. It states that every graph \(G\) contains the complete graph \(K_{\chi ( G )}\) as an immersion, and like its minor-order counterpart it is open even for graphs with independence number 2. We show that every graph \(G\) with independence number \(\alpha ( G ) \geq 2\) and no hole of length between 4 and \(2 \alpha ( G )\) satisfies this conjecture. In particular, every \(C_4\)-free graph \(G\) with \(\alpha ( G ) = 2\) satisfies the Lescure-Meyniel conjecture. We give another generalisation of this corollary, as follows. Let \(G\) and \(H\) be graphs with independence number at most 2, such that \(| V ( H ) | \leq 4\). If \(G\) is \(H\)-free, then \(G\) satisfies the Lescure-Meyniel conjecture.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abu-Khzam, F.; Langston, M., Graph coloring and the immersion order, (Warnow, T.; Zhu, B., Computing and Combinatorics. Computing and Combinatorics, Lecture Notes in Comput. Sci., vol. 2697 (2003), Springer: Springer Berlin, Heidelberg) · Zbl 1276.05042
[2] Blasiak, J., A special case of Hadwiger’s conjecture, J. Combin. Theory, Ser. B, 97, 1056-1073 (2007) · Zbl 1124.05082
[3] Bosse, C., A note on Hadwiger’s conjecture for \(W_5\)-free graphs with independence number two, Discrete Math., 342, 12, Article 111595 pp. (2019) · Zbl 1422.05079
[4] Bucić, M.; Fox, J.; Sudakov, B., Clique minors in graphs with a forbidden subgraph (2020), arXiv:2002.11100 [math.CO]
[5] Bustamante, S.; Quiroz, D. A.; Stein, M.; Zamora, J., Clique immersions and independence number (2019), arXiv:1907.01720 [math.CO]
[6] Catlin, P. A., Hajós’ graph-coloring conjecture: variations and counterexamples, J. Combin. Theory, Ser. B, 26, 268-274 (1979) · Zbl 0385.05033
[7] Chudnovsky, M.; Fradkin, A. O., Hadwiger’s conjecture for quasi-line graphs, J. Graph Theory, 59, 17-33 (2008) · Zbl 1175.05120
[8] Chudnovsky, M.; Seymour, P., Packing seagulls, Combinatorica, 32, 251-282 (2012) · Zbl 1289.05444
[9] DeVos, M.; Kawarabayashi, K.-i.; Mohar, B.; Okamura, H., Immersing small complete graphs, Ars Math. Contemp., 3, 2, 139-146 (2010) · Zbl 1213.05137
[10] Dirac, G. A., A property of 4-chromatic graphs and some remarks on critical graphs, J. Lond. Math. Soc., 27, 85-92 (1952) · Zbl 0046.41001
[11] Duchet, P.; Meyniel, H., On Hadwiger’s number and the stability number, Ann. Discrete Math., 13, 71-74 (1982) · Zbl 0522.05060
[12] Fox, J., Complete minors and independence number, SIAM J. Discrete Math., 24, 4, 1313-1321 (2010) · Zbl 1221.05289
[13] Füredi, Z.; Gyárfás, A.; Simonyi, G., Connected matchings and Hadwiger’s conjecture, Combin. Probab. Comput., 14, 435-438 (2005) · Zbl 1063.05104
[14] Gauthier, G.; Le, T.-N.; Wollan, P., Forcing clique immersions through chromatic number, European J. Combin., 81, 98-118 (2019) · Zbl 1420.05057
[15] Greenwood, R. E.; Gleason, A. M., Combinatorial relations and chromatic graphs, Canad. J. Math., 7, 1-7 (1955) · Zbl 0064.17901
[16] Guyer, M.; McDonald, J., On clique immersions in line graphs, Discrete Math., 343, 12, Article 112095 pp. (2020) · Zbl 1448.05169
[17] Hadwiger, H., Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich, 88, 133-143 (1943) · Zbl 0061.41308
[18] Kriesell, M., On Seymour’s strengthening of Hadwiger’s conjecture for graphs with certain forbidden subgraphs, Discrete Math., 310, 20, 2714-2724 (2010) · Zbl 1215.05070
[19] Lescure, F.; Meyniel, H., On a problem upon configurations contained in graphs with given chromatic number, Ann. Discrete Math., 41, 325-331 (1989) · Zbl 0675.05026
[20] Plummer, M. D.; Stiebitz, M.; Toft, B., On a special case of Hadwiger’s conjecture, Discuss. Math. Graph Theory, 23, 333-363 (2003) · Zbl 1053.05052
[21] Quiroz, D. A., Complete immersions in graphs with independence number two and small forbidden subgraphs. Proceedings of LAGOS 2021, Electron. Notes Theor. Comput. Sci. (2021), in press
[22] Reed, B.; Seymour, P., Hadwiger’s conjecture for line graphs, European J. Combin., 25, 6, 873-876 (2004) · Zbl 1050.05056
[23] Robertson, N.; Seymour, P., Graph minors XXIII Nash-Williams’ immersion conjecture, J. Combin. Theory, Ser. B, 100, 2, 181-205 (2010) · Zbl 1216.05151
[24] Seymour, P., Hadwiger’s conjecture, (Nash, J. F.; Rassias, M. Th., Open Problems in Mathematics (2016), Springer International Publishing) · Zbl 1347.05079
[25] Song, Z.-X.; Thomas, B., Hadwiger’s conjecture for graphs with forbidden holes, SIAM J. Discrete Math., 31, 3, 1572-1580 (2017) · Zbl 1368.05141
[26] Vergara, S., Complete graph immersions in dense graphs, Discrete Math., 340, 5, 1019-1027 (2017) · Zbl 1357.05072
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.