Complete minors, independent sets, and chordal graphs

DOI10.7151/DMGT.1571MaRDI QIDQ2906352zbMATH OpenOpenAlexFDO

Authors József Balogh, John Lenz, Hehui Wu

Publication date 5 September 2012

Published in Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

chordal graphsclique minorindependence numberHadwiger conjecture

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Abstract: The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) >= chi(G). Since chi(G) alpha(G) >= |V(G)|, Hadwiger's Conjecture implies that alpha(G) h(G) >= |V(G)|. We show that (2 alpha(G) - lceil log_t(t alpha(G)/2) ceil) h(G) geq |V(G)| where t is approximately 6.83. For graphs with alpha(G) geq 14, this improves on a recent result of Kawarabayashi and Song who showed (2 alpha(G) - 2) h(G) >= |V(G)| when alpha(G) >= 3.

Recommendations

• Independence number and clique minors
• Complete minors and independence number
• Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture
• Clique minors in claw-free graphs
• Large minors in graphs with given independence number

Cited in

(11)

• scientific article; zbMATH DE number 5059933 (Why is no real title available?)
• A basic elementary extension of the Duchet-Meyniel theorem
• Complete minors in complements of nonseparating planar graphs
• On a relationship between Hadwiger and stability numbers
• Large immersions in graphs with independence number 3 and 4
• Clique minors in graphs with a forbidden subgraph
• Clique immersions and independence number
• Independence number and clique minors
• Large minors in graphs with given independence number
• The Hadwiger number, chordal graphs and \(ab\)-perfection
• Complete minors and independence number

This page was built for publication: Complete minors, independent sets, and chordal graphs

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