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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom