Back to Search Start Over

A note on Hadwiger's conjecture for [formula omitted]-free graphs with independence number two.

Authors :
Bosse, Christian
Source :
Discrete Mathematics. Dec2019, Vol. 342 Issue 12, pN.PAG-N.PAG. 1p.
Publication Year :
2019

Abstract

The Hadwiger number of a graph G , denoted h (G) , is the largest integer t such that G contains K t as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph G , h (G) ≥ χ (G) , where χ (G) denotes the chromatic number of G. Let α (G) denote the independence number of G. A graph is H - free if it does not contain the graph H as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that h (G) ≥ χ (G) for all H -free graphs G with α (G) ≤ 2 , where H is any graph on four vertices with α (H) ≤ 2 , H = C 5 , or H is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs H on five vertices with α (H) ≤ 2. In this note, we prove that h (G) ≥ χ (G) for all W 5 -free graphs G with α (G) ≤ 2 , where W 5 denotes the wheel on six vertices. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
0012365X
Volume :
342
Issue :
12
Database :
Academic Search Index
Journal :
Discrete Mathematics
Publication Type :
Academic Journal
Accession number :
139074033
Full Text :
https://doi.org/10.1016/j.disc.2019.07.011