Clique minors in double‐critical graphs
Martin Rolek, Zi‐Xia Song · Journal of Graph Theory · 2017
Abstract A connected t ‐chromatic graph G is double‐critical if is ‐colorable for each edge . 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 . 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 minor and verified their conjecture for . Albar and Gonçalves recently proved that every double‐critical 8‐chromatic graph contains a K 8 minor, and their proof is computer assisted. In this article, we prove that every double‐critical t ‐chromatic graph contains a minor for all . Our proof for is shorter and computer free.