Clique immersions in graphs of independence number two with certain forbidden subgraphs

DOI10.1016/J.DISC.2021.112365zbMATH Open1462.05285arXiv2004.05433OpenAlexW3138725079MaRDI QIDQ2022152FDOQ2022152

Authors: Daniel A. Quiroz 

Publication date: 28 April 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The Lescure-Meyniel conjecture is the analogue of Hadwiger's conjecture for the immersion order. It states that every graph $G$ contains the complete graph $K_{chi(G)}$ as an immersion, and like its minor-order counterpart it is open even for graphs with independence number 2. We show that every graph $G$ with independence number $alpha(G)ge2$ and no hole of length between $4$ and $2alpha(G)$ satisfies this conjecture. In particular, every $C_4$-free graph $G$ with $alpha(G)=2$ satisfies the Lescure-Meyniel conjecture. We give another generalisation of this corollary, as follows. Let $G$ and $H$ be graphs with independence number at most 2, such that $|V(H)|le4$. If $G$ is $H$-free, then $G$ satisfies the Lescure-Meyniel conjecture.

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

Recommendations

• Clique immersions and independence number
• Clique immersion in graphs without a fixed bipartite graph
• Complete graph immersions in dense graphs
• Clique minors in graphs with a forbidden subgraph
• Hadwiger's conjecture for graphs with forbidden holes

zbMATH Keywords

chromatic numberHadwiger's conjecturecliqueindependence numberforbidden subgraphsgraph immersion

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Packing seagulls
• Hadwiger's conjecture
• On a special case of Hadwiger's conjecture
• Title not available (Why is that?)
• Combinatorial Relations and Chromatic Graphs
• Graph coloring and the immersion order
• Immersing small complete graphs
• On Hadwiger's Number and the Stability Number
• Title not available (Why is that?)
• Graph minors XXIII. Nash-Williams' immersion conjecture
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Complete graph immersions in dense graphs
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Hadwiger's conjecture for line graphs
• A special case of Hadwiger's conjecture
• Hadwiger's conjecture for quasi-line graphs
• Complete minors and independence number
• On Seymour's strengthening of Hadwiger's conjecture for graphs with certain forbidden subgraphs
• Connected matchings and Hadwiger's conjecture
• On clique immersions in line graphs
• A note on Hadwiger's conjecture for \(W_5\)-free graphs with independence number two
• Hadwiger's conjecture for graphs with forbidden holes

Cited In (4)

• Biclique immersions in graphs with independence number 2
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• Clique immersion in graphs without a fixed bipartite graph
• Clique immersions and independence number

This page was built for publication: Clique immersions in graphs of independence number two with certain forbidden subgraphs

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