Six-colorability of graphs excluding the near-complete minor $K_7^-$: the surviving level-7 instance of Seymour's H-Hadwiger conjecture

Hadwiger's 1943 conjecture asserts that every graph with no $K_t$ minor is $(t-1)$-colorable; it is proved for $t \le 6$, and $t = 7$ is the first open level. A suggested weakening due to Seymour, the H-Hadwiger conjecture, predicts that for every graph $H$ on $t$ vertices, every graph with no $H$ minor is $(t-1)$-colorable. For the three graphs on seven vertices obtained from $K_7$ by deleting one or two edges --- $K_7^-$ (one edge deleted), $K_7^=$ (two independent edges deleted), and $K_7^{\vee}$ (two adjacent edges deleted) --- it predicts 6-colorability. A 1971 theorem settled the case where both $K_7^{\vee}$ and $K_7^=$ are excluded, and in 2025 Norin and Totschnig proved that every graph with no $K_7^{\vee}$ minor is 6-colorable. The source paper of Lafferty and Song (2022) recorded as open the 6-colorability of graphs with no $K_7^=$ minor and of graphs with no $K_7^-$ minor, restated as Conjectures 19 and 21 of Norin and Totschnig (2025). The first of those two was settled in 2026: Dvořák, Norin and Rahman (arXiv:2609.17760) proved that every graph with no $K_7^=$ minor is 6-colorable, leaving the $K_7^-$ statement as the surviving level-7 instance. The $K_7^-$ statement implies the $K_7^=$ statement, and the best known bound for graphs with no $K_7^-$ minor is 7-colorability.

Background

A graph $H$ is a minor of a graph $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges (merging their endpoints); $G$ has no $H$ minor if no such model exists. The chromatic number $\chi(G)$ is the least number of colors needed to color the vertices so that adjacent vertices receive different colors. Hadwiger's conjecture (1943) states that every graph with no $K_t$ minor ($K_t$ being the complete graph on $t$ vertices) is $(t-1)$-colorable. It is equivalent to the Four Color Theorem for $t = 5$ and was proved for $t = 6$ by Robertson, Seymour and Thomas (1993); it remains open for all $t \ge 7$, and a survey by Seymour (2016) records its status. At the first open level $t = 7$, even 7-colorability of graphs with no $K_7$ minor is open: Albar and Gonçalves (2018) proved that every graph with no $K_7$ minor is 8-colorable, and no better bound is known.

Given this difficulty, Paul Seymour suggested in 2017 the study of a weakening (recorded as Conjecture 1.2 in Lafferty and Song 2022 and discussed in Norin and Totschnig 2025), now called the H-Hadwiger conjecture: for every graph $H$ on $t$ vertices, every graph with no $H$ minor is $(t-1)$-colorable. For $H = K_t$ this is Hadwiger's conjecture; for any other $H$ on $t$ vertices, excluding $H$ is a weaker restriction than excluding $K_t$ (every graph with no $K_t$ minor also has no $H$ minor, since $H$ is a subgraph of $K_t$), so the statement is weaker than Hadwiger's conjecture at level $t$ and serves as a stepping stone toward it.

We consider the near-complete 7-vertex graphs. Write $K_7^-$ for $K_7$ with one edge deleted; $K_7^=$ for $K_7$ with two independent edges deleted (a matching of size two); and $K_7^{\vee}$ for $K_7$ with two adjacent edges deleted (two edges sharing a vertex). The H-Hadwiger conjecture predicts that graphs excluding any one of these are 6-colorable. The classical anchor is a 1971 theorem of Jakobsen, stated as Theorem 2 of Norin and Totschnig (2025) and also recorded in the abstract of Lafferty and Song (2022): every graph with no $K_7^{\vee}$ minor and no $K_7^=$ minor is 6-colorable. Jakobsen also proved in 1971 that every graph with no $K_7^-$ minor is 7-colorable (as recorded by Lafferty and Song), and Albar (2014) gave a new proof of this bound, which remains the best known for the class. The source paper, Lafferty and Song (2022), proves that every graph with no $\mathcal{K}_9^{-6}$ minor is 8-colorable (where $\mathcal{K}_9^{-6}$ is the family of all graphs obtained from $K_9$ by deleting six edges) and explicitly lists as open the 6-colorability of graphs excluding each of $K_7^-$, $K_7^=$ and $K_7^<$ (their notation for $K_7^{\vee}$), along with 7-colorability of graphs with no $K_7$ minor, the 8-connectivity of $k$-contraction-critical graphs for $k \ge 8$, and extensions of their deletion-family sequence. In July 2025, Norin and Totschnig resolved the adjacent-deletion case: every graph with no $K_7^{\vee}$ minor is 6-colorable. Their proof rests on a new extremal theorem (every 4-connected graph $G$ with $|E(G)| \ge 4|V(G)| - 8$ has a $K_7^{\vee}$ minor unless $G$ is isomorphic to $K_{2,2,2,2}$, the complete multipartite graph with four parts of size two), and they document an obstruction to extending it: the direct analogue for $K_7^=$ fails, since their graphs $G_n$ (a universal 4-vertex set joined to a matching on the remaining vertices) are 4-connected with $4|V| + \lfloor |V|/2 \rfloor - 12 \ge 4|V| - 8$ edges and still have no $K_7^=$ minor. They pose Conjecture 19 (every graph with no $K_7^=$ minor is 6-colorable), Conjecture 20 (a possible 5-connected extremal analogue: every 5-connected graph with at least $4|V| - 9$ edges has a $K_7^=$ minor unless it is $K_6$), and Conjecture 21 (every graph with no $K_7^-$ minor is 6-colorable), which they call a natural common strengthening of their theorem and Conjecture 19. Conjecture 19 has since been settled: Dvořák, Norin and Rahman (arXiv:2609.17760, 2026) proved that every graph with no $K_7^=$ minor is 6-colorable, while Conjectures 20 and 21 remain open.

Problem Statement

Let $K_7^-$ denote the complete graph $K_7$ with one edge deleted, and let $K_7^=$ denote $K_7$ with two independent edges deleted (a matching of size two). Decide the following statement, the surviving instance of Seymour's H-Hadwiger conjecture for 7-vertex graphs obtained from $K_7$ by deleting at most two edges, which the source paper of Lafferty and Song (2022) records as open (restated as Conjecture 21 by Norin and Totschnig, 2025):

(1) Is every graph with no $K_7^-$ minor 6-colorable?

This is the stronger of the two statements that Lafferty and Song (2022) recorded as open: $K_7^=$ is a subgraph of $K_7^-$, so any graph containing a $K_7^-$ minor also contains a $K_7^=$ minor; hence every graph with no $K_7^=$ minor also has no $K_7^-$ minor, and an affirmative answer to (1) settles the 6-colorability of graphs with no $K_7^=$ minor as well. That weaker statement is no longer open: Dvořák, Norin and Rahman (arXiv:2609.17760, 2026) proved that every graph with no $K_7^=$ minor is 6-colorable. A complete answer to the statement posed above decides it: it is either proved for all graphs, or refuted by an explicit finite graph with chromatic number at least 7 and no $K_7^-$ minor.

References

1. Michael Lafferty and Zi-Xia Song (2022), "Every graph with no $\mathcal{K}_9^{-6}$ minor is $8$-colorable", arXiv:2209.05259, DOI 10.48550/arXiv.2209.05259, https://arxiv.org/abs/2209.05259
2. Sergey Norin and Agnes Totschnig (2025), "Every graph with no $K_7^{\vee}$-minor is $6$-colorable", arXiv:2507.03244, https://arxiv.org/abs/2507.03244
3. Michael Lafferty, Runrun Liu, Martin Rolek and Gexin Yu (2025), "Connectivity of contraction-critical graphs", arXiv:2509.07144, https://arxiv.org/abs/2509.07144
4. Martin Rolek, Zi-Xia Song and Robin Thomas (2023), "Properties of $8$-contraction-critical graphs with no $K_7$ minor", European Journal of Combinatorics 110:103711, DOI 10.1016/j.ejc.2023.103711, https://doi.org/10.1016/j.ejc.2023.103711 (also arXiv:2208.07335)
5. Boris Albar (2014), "Coloration of $K_7^-$-minor free graphs", arXiv:1402.2806, https://arxiv.org/abs/1402.2806
6. Boris Albar and Daniel Gonçalves (2018), "On triangles in $K_7$-minor free graphs", Journal of Graph Theory 88(1):154-173, DOI 10.1002/jgt.22203, https://doi.org/10.1002/jgt.22203
7. Neil Robertson, Paul Seymour and Robin Thomas (1993), "Hadwiger's conjecture for $K_6$-free graphs", Combinatorica 13(3):279-361, DOI 10.1007/BF01202354, https://doi.org/10.1007/BF01202354
8. Wolfgang Mader (1968), "Über trennende Eckenmengen in homomorphiekritischen Graphen", Mathematische Annalen 175:243-252, DOI 10.1007/BF02052726, https://doi.org/10.1007/BF02052726
9. Paul Seymour (2016), "Hadwiger's Conjecture", chapter 13, pages 417-437 in Open Problems in Mathematics, Springer, Cham, DOI 10.1007/978-3-319-32162-2_13, https://doi.org/10.1007/978-3-319-32162-2_13
10. Martin Rolek (2020), "Graphs with no $K_9^=$ minor are 10-colorable", Journal of Graph Theory 93(4):560-565, DOI 10.1002/jgt.22502, https://doi.org/10.1002/jgt.22502
11. Olivier Fischer and Raphael Steiner (2023), "On the choosability of $H$-minor-free graphs", arXiv:2304.04246, https://arxiv.org/abs/2304.04246
12. Sergey Norin and Jérémie Turcotte (2025), "Limits of degeneracy for colouring graphs with forbidden minors", Transactions of the American Mathematical Society 378(9):6425-6451, DOI 10.1090/tran/9493, https://doi.org/10.1090/tran/9493 (also arXiv:2304.13715)
13. Zdeněk Dvořák, Sergey Norin and Neil Rahman (2026), "Every graph with no $K_7^=$ minor is $6$-colorable", arXiv:2609.17760, DOI 10.48550/arXiv.2609.17760, https://arxiv.org/abs/2609.17760