Coloring Graphs With Forbidden Minors

Keywords

Contraction-critical graph; Graph minor; Hadwiger's conjecture

Abstract

Hadwiger's conjecture from 1943 states that for every integer t≥1, every graph either can be t-colored or has a subgraph that can be contracted to the complete graph on t+1 vertices. As pointed out by Paul Seymour in his recent survey on Hadwiger's conjecture, proving that graphs with no K7 minor are 6-colorable is the first case of Hadwiger's conjecture that is still open. It is not known yet whether graphs with no K7 minor are 7-colorable. Using a Kempe-chain argument along with the fact that an induced path on three vertices is dominating in a graph with independence number two, we first give a very short and computer-free proof of a recent result of Albar and Gonçalves and generalize it to the next step by showing that every graph with no Kt minor is (2t−6)-colorable, where t∈{7,8,9}. We then prove that graphs with no K8− minor are 9-colorable, and graphs with no K8= minor are 8-colorable. Finally we prove that if Mader's bound for the extremal function for Kt minors is true, then every graph with no Kt minor is (2t−6)-colorable for all t≥6. This implies our first result. We believe that the Kempe-chain method we have developed in this paper is of independent interest.

Publication Date

11-1-2017

Publication Title

Journal of Combinatorial Theory. Series B

Volume

127

Number of Pages

14-31

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.jctb.2017.05.001

Socpus ID

85019573201 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85019573201

This document is currently not available here.

Share

COinS