Biclique immersions in graphs with independence number 2

arXiv2303.06483MaRDI QIDQ6429210FDOQ6429210

Authors: F. Botler, Andrea Jiménez, Carla Negri Lintzmayer, Adrián Pastine, Daniel A. Quiroz, Maycon Sambinelli 

Publication date: 11 March 2023

Abstract: The analog 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_{lceiln/2ceil}$. We show that every $n$-vertex graph with independence number 2 contains every complete bipartite graph on $lceiln/2ceil$ vertices as an immersion.

This page was built for publication: Biclique immersions in graphs with independence number 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429210)