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

DOI10.1016/J.DISC.2021.112365MaRDI QIDQ2022152zbMATH OpenOpenAlexFDO

Authors Daniel A. Quiroz

Publication date 28 April 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(5)

• Large immersions in graphs with independence number 3 and 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)