Premium
Graphs with no K 9 = minor are 10‐colorable
Author(s) -
Rolek Martin
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22502
Subject(s) - combinatorics , minor (academic) , mathematics , conjecture , 1 planar graph , graph minor , graph , robertson–seymour theorem , indifference graph , discrete mathematics , chordal graph , line graph , graph power , political science , law
Hadwiger's conjecture claims that any graph with no K t minor is ( t − 1 ) ‐colorable. This has been proved for t ≤ 6 , but remains open for t ≥ 7 . As a variant of this conjecture, graphs with no K t = minor have been considered, where K t = denotes the complete graph with two edges removed. It has been shown that graphs with no K t = minor are ( 2 t − 8 ) ‐colorable for t ∈ { 7 , 8 } . In this paper, we extend this result to the case t = 9 and show that graphs with no K 9 = minor are 10 ‐colorable.