Biclique immersions in graphs with independence number 2
EUROCOMB’23
169–177
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

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Fábio Botler, Andrea Jiménez, Carla N. Lintzmayer, Adrián Pastine, Daniel A. Quiroz, Maycon Sambinelli