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 numbercliqueforbidden subgraphsgraph immersionHadwiger's conjectureindependence number

Mathematics Subject Classification ID

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

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

• A note on Hadwiger's conjecture for \(W_5\)-free graphs with independence number two
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• 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
• scientific article; zbMATH DE number 4104981 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• Immersing small complete graphs
• On a special case of Hadwiger's conjecture
• On clique immersions in line graphs
• On Hadwiger's Number and the Stability Number
• On Seymour's strengthening of Hadwiger's conjecture for graphs with certain forbidden subgraphs
• Packing seagulls

Cited in

(7)

• Large immersions in graphs with independence number 3 and 4
• Clique immersion in graphs without a fixed bipartite graph
• Clique immersions and independence number
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• Biclique immersions in graphs with independence number 2
• Complete bipartite immersion in graphs with independence number two: a simple proof
• Biclique immersions in graphs with independence number 2 (extended abstract)

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)