A basic elementary extension of the Duchet-Meyniel theorem

DOI10.1016/J.DISC.2009.03.023MaRDI QIDQ960956zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Anders Sune Pedersen, Bjarne Toft

Publication date 29 March 2010

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complete minorsindependence numberHadwiger number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph minors (05C83)

Abstract: The Conjecture of Hadwiger implies that the Hadwiger number $h$ times the independence number $alpha$ of a graph is at least the number of vertices $n$ of the graph. In 1982 Duchet and Meyniel proved a weak version of the inequality, replacing the independence number $alpha$ by $2alpha-1$, that is, ${\displaystyle }$(2alpha-1)cdot h geq n.${\displaystyle }$ In 2005 Kawarabayashi, Plummer and the second author published an improvement of the theorem, replacing $2alpha-1$ by $2alpha-3/2$ when $alpha$ is at least 3. Since then a further improvement by Kawarabayashi and Song has been obtained, replacing $2alpha-1$ by $2alpha-2$ when $alpha$ is at least 3. In this paper a basic elementary extension of the Theorem of Duchet and Meyniel is presented. This may be of help to avoid dealing with basic cases when looking for more substantial improvements. The main unsolved problem (due to Seymour) is to improve, even just slightly, the theorem of Duchet and Meyniel in the case when the independence number $alpha$ is equal to 2. The case $alpha=2$ of Hadwiger's Conjecture was first pointed out by Mader as an interesting special case.

Recommendations

• Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture
• Independence number and clique minors
• Complete minors, independent sets, and chordal graphs
• Complete minors and independence number
• A note on Hadwiger's conjecture for \(W_5\)-free graphs with independence number two

Cites work

• scientific article; zbMATH DE number 1156585 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• A short proof of a theorem of dirac's about hadwiger's conjecture
• Graph theory
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture
• Independent sets in graphs with an excluded clique minor
• On Hadwiger's Number and the Stability Number
• On a relationship between Hadwiger and stability numbers
• On a special case of Hadwiger's conjecture
• Subcontraction-equivalence and Hadwiger's conjecture

Cited in

(1)

• Clique minors in graphs with a forbidden subgraph

This page was built for publication: A basic elementary extension of the Duchet-Meyniel theorem

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