Biclique immersions in graphs with independence number 2

EUROCOMB’23

Abstract
The analogue of Hadwiger‘s Conjecture for the immersion relation states that every graph $G$ contains an immersion of $K_{\chi(G)}$. For graphs with independence number 2, this is equivalent to stating that every such $n$-vertex graph contains an immersion of $K_{\lceil n/2 \rceil}$. We show that every $n$-vertex graph with independence number 2 contains every complete bipartite graph on $\lceil n/2 \rceil$ vertices as an immersion.

Pages:
169–177
References

Faisal N. Abu-Khzam and Michael A. Langston. Graph coloring and the immersion order. In Computing and combinatorics, volume 2697 of Lecture Notes in Comput. Sci., pages 394-403. Springer, Berlin, 2003.
https://doi.org/10.1007/3-540-45071-8_40

F. Botler, A. Jiménez, C. N. Lintzmayer, A. Pastine, D. A. Quiroz, and M. Sambinelli. Biclique immersions in graphs with independence number 2. arXiv:2303.06483 [math.CO], 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-024

Sebastián Bustamante, Daniel A. Quiroz, Maya Stein, and José Zamora. Clique immersions and independence number. European J. Combin., 106:Paper No. 103550, 9, 2022.
https://doi.org/10.1016/j.ejc.2022.103550

Matt DeVos, Zdenek Dvorák, Jacob Fox, Jessica McDonald, Bojan Mohar, and Diego Scheide. A minimum degree condition forcing complete graph immersion. Combinatorica, 34:279-298, 2014.
https://doi.org/10.1007/s00493-014-2806-z

Matt DeVos, Ken-ichi Kawarabayashi, Bojan Mohar, and Haruko Okamura. Immersing small complete graphs. Ars Math. Contemp., 3(2):139-146, 2010.
https://doi.org/10.26493/1855-3974.112.b74

Matt DeVos, Jessica McDonald, Bojan Mohar, and Diego Scheide. Immersing complete digraphs. European J. Combin., 33(6):1294-1302, 2012.
https://doi.org/10.1016/j.ejc.2012.02.002

G. A. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc., 27:85-92, 1952.
https://doi.org/10.1112/jlms/s1-27.1.85

P. Duchet and H. Meyniel. On Hadwiger's number and the stability number. Ann. Discrete Math., 13:71-73, 1982.
https://doi.org/10.1016/S0304-0208(08)73549-7

Zdenek Dvorák and Paul Wollan. A structure theorem for strong immersions. J. Graph Theory, 83(2):152-163, 2016.
https://doi.org/10.1002/jgt.21990

Zdenek Dvorák and Liana Yepremyan. Complete graph immersions and minimum degree. J. Graph Theory, 88(1):211-221, 2018.
https://doi.org/10.1002/jgt.22206

Jacob Fox. Complete minors and independence number. SIAM J. Discrete Math., 24(4):1313-1321, 2010.
https://doi.org/10.1137/090766814

Gregory Gauthier, Tien-Nam Le, and Paul Wollan. Forcing clique immersions through chromatic number. European J. Combin., 81:98-118, 2019.
https://doi.org/10.1016/j.ejc.2019.04.003

H. Hadwiger. Über eine Klassifikation der Streckenkomplexe. Vierteljschr. Naturforsch. Ges. Zürich, 88:133-142, 1943.

Ken-ichi Kawarabayashi, Michael D. Plummer, and Bjarne Toft. Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture. J. Combin. Theory Ser. B, 95(1):152-167, 2005.
https://doi.org/10.1016/j.jctb.2005.04.001

Ken-ichi Kawarabayashi and Zi-Xia Song. Independence number and clique minors. J. Graph Theory, 56(3):219-226, 2007.
https://doi.org/10.1002/jgt.20268

A. V. Kostochka. On K_{s,t} minors in (s + t)-chromatic graphs. J. Graph Theory, 65(4):343-350, 2010.
https://doi.org/10.1002/jgt.20485

A. V. Kostochka. K_{s,t} minors in (s + t)-chromatic graphs, II. J. Graph Theory, 75(4):377-386, 2014.
https://doi.org/10.1002/jgt.21744

A. V. Kostochka and N. Prince. Dense graphs have K_{3,t} minors. Discrete Math., 310(20):2637-2654, 2010.
https://doi.org/10.1016/j.disc.2010.03.026

F. Lescure and H. Meyniel. On a problem upon con gurations contained in graphs with given chromatic number. Ann. Discrete Math., 41:325-331, 1989.
https://doi.org/10.1016/S0167-5060(08)70470-9

Chun-Hung Liu. Immersion and clustered coloring. J. Combin. Theory, Ser. B, 158(1):252-282, 2023.
https://doi.org/10.1016/j.jctb.2022.07.010

Chun-Hung Liu and Irene Muzi. Well-quasi-ordering digraphs with no long alternating paths by the strong immersion relation. J. Combin. Theory, Ser. B, 158(1):210-251, 2023.
https://doi.org/10.1016/j.jctb.2022.08.007

Dániel Marx and Paul Wollan. Immersions in highly edge connected graphs. SIAM J. Discrete Math., 28(1):503-520, 2014.
https://doi.org/10.1137/130924056

Sergey Norin and Paul Seymour. Dense minors of graphs with independence number two, 2022. arXiv:2206.00186 [math.CO].

Michael D. Plummer, Michael Stiebitz, and Bjarne Toft. On a special case of Hadwiger's conjecture. Discuss. Math. Graph Theory, 23(2):333-363, 2003.
https://doi.org/10.7151/dmgt.1206

Daniel A. Quiroz. Clique immersions in graphs of independence number two with certain forbidden subgraphs. Discrete Math., 344(6):Paper No. 112365, 9, 2021.
https://doi.org/10.1016/j.disc.2021.112365

Neil Robertson and Paul Seymour. Graph minors XXIII. Nash-Williams' immersion conjecture. J. Combin. Theory, Ser. B, 100(2):181-205, 2010.
https://doi.org/10.1016/j.jctb.2009.07.003

Neil Robertson, Paul Seymour, and Robin Thomas. Hadwiger's conjecture for K6-free graphs. Combinatorica, 13(3):279-361, 1993.
https://doi.org/10.1007/BF01202354

Paul Seymour. Hadwiger's conjecture. In Open problems in mathematics, pages 417-437. Springer, [Cham], 2016.
https://doi.org/10.1007/978-3-319-32162-2_13

Matej Stehlík. Critical graphs with connected complements. J. Combin. Theory Ser. B, 89(2):189-194, 2003.
https://doi.org/10.1016/S0095-8956(03)00069-8

Sylvia Vergara. Complete graph immersions in dense graphs. Discrete Math., 340(5):1019-1027, 2017.
https://doi.org/10.1016/j.disc.2017.01.001

Paul Wollan. The structure of graphs not admitting a xed immersion. J. Combin. Theory, Ser. B, 110(1):47-66, 2016.
https://doi.org/10.1016/j.jctb.2014.07.003

David R. Wood. Independent sets in graphs with an excluded clique minor. Discrete Math. Theor. Comput. Sci., 9(1):171-175, 2007.
https://doi.org/10.46298/dmtcs.385

Douglas R. Woodall. List colourings of graphs. In Surveys in combinatorics, 2001 (Sussex), volume 288 of London Math. Soc. Lecture Note Ser., pages 269-301. Cambridge Univ. Press, Cambridge, 2001.
https://doi.org/10.1017/CBO9780511721328.012

Metrics

0

Views

0

PDF views