Clique Minors In Double-Critical Graphs

Keywords

clique minor; double-critical graph; separating set

Abstract

A connected t-chromatic graph G is double-critical if G - { u,v } is (t-2) -colorable for each edge ∈ E(G). A long-standing conjecture of Erdős and Lovász that the complete graphs are the only double-critical t-chromatic graphs remains open for all t ≥ 6. Given the difficulty in settling Erdős and Lovász's conjecture and motivated by the well-known Hadwiger's conjecture, Kawarabayashi, Pedersen, and Toft proposed a weaker conjecture that every double-critical t-chromatic graph contains a Kt minor and verified their conjecture for t ≤ 7. Albar and Gonçalves recently proved that every double-critical 8-chromatic graph contains a K8 minor, and their proof is computer assisted. In this article, we prove that every double-critical t-chromatic graph contains a Kt minor for all t ≤ 9 Our proof for t ≤ 8 is shorter and computer free.

Publication Date

6-1-2018

Publication Title

Journal of Graph Theory

Volume

88

Issue

2

Number of Pages

347-355

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1002/jgt.22216

Socpus ID

85034272196 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS