Back to Search
Start Over
A note on Hadwiger's conjecture for [formula omitted]-free graphs with independence number two.
- 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]
- Subjects :
- *LOGICAL prediction
*INTEGERS
*MATROIDS
Subjects
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