English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Hadwiger's Conjecture from 1943 states that every graph with no $K_{t}$ minoris $(t-1)$-colorable; it remains wide open for all $t\ge 7$. For positiveintegers $t$ and $s$, let $\mathcal{K}_t^{-s}$ denote the family of graphsobtained from the complete graph $K_t$ by removing $s$ edges. We say that agraph $G$ has no $\mathcal{K}_t^{-s}$ minor if it has no $H$ minor for every$H\in \mathcal{K}_t^{-s}$. Jakobsen in 1971 proved that every graph with no$\mathcal{K}_7^{-2}$ minor is $6$-colorable. In this paper we consider the nextstep and prove that every graph with no $\mathcal{K}_8^{-4}$ minor is$7$-colorable. Our result implies that $H$-Hadwiger's Conjecture, suggested byPaul Seymour in 2017, is true for every graph $H$ on eight vertices such thatthe complement of $H$ has maximum degree at least four, a perfect matching, atriangle and a cycle of length four. Our proof utilizes an extremal functionfor $\mathcal{K}_8^{-4}$ minors obtained in this paper, generalized Kempechains of contraction-critical graphs by Rolek and the second author, and themethod for finding $K_7$ minors from three different $K_5$ subgraphs byKawarabayashi and Toft; this method was first developed by Robertson, Seymourand Thomas in 1993 to prove Hadwiger's Conjecture for $t=6$.

Every graph with no $\mathcal{K}_8^{-4}$ minor is $7$-colorable