Complete minors, independent sets, and chordal graphs

DOI10.7151/DMGT.1571zbMATH Open1255.05184arXiv0907.2421OpenAlexW2963039457MaRDI QIDQ2906352FDOQ2906352

Authors: József Balogh, John Lenz, Hehui Wu 

Publication date: 5 September 2012

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

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.

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

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

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)

Cited In (10)

• Complete minors in complements of nonseparating planar graphs
• A basic elementary extension of the Duchet-Meyniel theorem
• 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
• Title not available (Why is that?)
• 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)