Clique immersion in graphs without a fixed bipartite graph

DOI10.1016/J.JCTB.2022.07.008zbMATH Open1497.05183arXiv2011.10961OpenAlexW4292262955MaRDI QIDQ2171024FDOQ2171024

Hong Liu, Donglei Yang, Guanghui Wang

Publication date: 23 September 2022

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

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.

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

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
• Forcing clique immersions through chromatic number

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)

Cites Work

• A bound on the chromatic number of a graph
• The extremal function for complete minors
• Lower bound of the Hadwiger number of graphs by their average degree
• Minors in expanding graphs
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• On a problem of K. Zarankiewicz
• Title not available (Why is that?)
• Topological cliques in graphs II
• Graph Coloring and the Immersion Order
• Immersing small complete graphs
• Title not available (Why is that?)
• A minimum degree condition forcing complete graph immersion
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Constructing graphs with no immersion of large complete graphs
• Complete graph immersions and minimum degree
• Title not available (Why is that?)
• Complete minors in \(K_{s,s}\)-free graphs
• A proof of Mader's conjecture on large clique subdivisions in C4-free graphs
• Forcing clique immersions through chromatic number

Cited In (13)

• Immersion of complete digraphs in Eulerian digraphs
• Separating path systems of almost linear size
• Disjoint isomorphic balanced clique subdivisions
• How to build a pillar: a proof of Thomassen's conjecture
• 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
• Crux and Long Cycles in Graphs
• Clique immersions and independence number
• Crux, space constraints and subdivisions
• Towards the Erdős-Gallai cycle decomposition conjecture
• Well-mixing vertices and almost expanders
• 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)