A basic elementary extension of the Duchet-Meyniel theorem

DOI10.1016/J.DISC.2009.03.023zbMATH Open1215.05176DBLPjournals/dm/PedersenT10arXiv0810.0846OpenAlexW2011848820WikidataQ59713076 ScholiaQ59713076MaRDI QIDQ960956FDOQ960956

Authors: Anders Sune Pedersen, Bjarne Toft 

Publication date: 29 March 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

complete minorsindependence numberHadwiger number

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• On a special case of Hadwiger's conjecture
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Title not available (Why is that?)
• On Hadwiger's Number and the Stability Number
• Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture
• Independent sets in graphs with an excluded clique minor
• Title not available (Why is that?)
• Subcontraction-equivalence and Hadwiger's conjecture
• On a relationship between Hadwiger and stability numbers
• A short proof of a theorem of dirac's about 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)