Clique immersion in graphs without a fixed bipartite graph

DOI10.1016/J.JCTB.2022.07.008MaRDI QIDQ2171024zbMATH OpenOpenAlexFDO

Authors Hong Liu, Donglei Yang, Guanghui Wang

Publication date 23 September 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.10961

zbMATH Keywords

average degreegraph immersionssublinear expander

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Abstract: A graph $G$ contains $H$ as an emph{immersion} if there is an injective mapping $phi:V(H)ightarrowV(G)$ such that for each edge $uvinE(H)$, there is a path $P_{uv}$ in $G$ joining vertices $phi(u)$ and $phi(v)$, and all the paths $P_{uv}$, $uvinE(H)$, are pairwise edge-disjoint. An analogue of Hadwiger's conjecture for the clique immersions by Lescure and Meyniel, and independently by Abu-Khzam and Langston, states that every graph $G$ contains $K_{chi(G)}$ as an immersion. We prove that for any constant $varepsilon>0$ and integers $s,tge2$, there exists $d_0=d_0(varepsilon,s,t)$ such that every $K_{s,t}$-free graph $G$ with $d(G)ge{d}_0$ contains a clique immersion of order $(1-varepsilon)d(G)$. This implies that the above-mentioned conjecture is asymptotically true for graphs without a fixed complete bipartite graph.

Recommendations

• Clique immersions and independence number
• Clique immersions in graphs of independence number two with certain forbidden subgraphs
• Complete graph immersions in dense graphs
• Constructing graphs with no immersion of large complete graphs

Cites work

• scientific article; zbMATH DE number 4104981 (Why is no real title available?)
• scientific article; zbMATH DE number 3232673 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• A bound on the chromatic number of a graph
• A minimum degree condition forcing complete graph immersion
• A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
• Complete graph immersions and minimum degree
• Complete minors in \(K_{s,s}\)-free graphs
• Constructing graphs with no immersion of large complete graphs
• Graph coloring and the immersion order
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Immersing small complete graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• Minors in expanding graphs
• On a problem of K. Zarankiewicz
• The extremal function for complete minors
• Topological cliques in graphs II

Cited in

(18)

• A note on forbidding clique immersions
• Immersion of complete digraphs in Eulerian digraphs
• On clique immersions in line graphs
• Separating path systems of almost linear size
• Disjoint isomorphic balanced clique subdivisions
• Clique immersions in graphs of independence number two with certain forbidden subgraphs
• How to build a pillar: a proof of Thomassen's conjecture
• Biclique immersions in graphs with independence number 2
• Towards the Erdős-Gallai cycle decomposition conjecture
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• Many Hamiltonian subsets in large graphs with given density
• A note on clique immersion of strong product graphs
• Crux and Long Cycles in Graphs
• Clique immersions and independence number
• Crux, space constraints and subdivisions
• Well-mixing vertices and almost expanders
• Towards the Erdős-Gallai cycle decomposition conjecture
• Clique immersion in graph products

This page was built for publication: Clique immersion in graphs without a fixed bipartite graph

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