Hadwiger's 1943 conjecture asserts that every graph with no KtK_t minor is (t−1)(t-1)-colorable; it is proved for t≤6t \le 6, and t=7t = 7 is the first open level. A suggested weakening due to Seymour, the H-Hadwiger conjecture, predicts that for every graph HH on tt vertices, every graph with no HH minor is (t−1)(t-1)-colorable. For the three graphs on seven vertices obtained from K7K_7 by deleting one or two edges --- K7−K_7^- (one edge deleted), K7=K_7^= (two independent edges deleted), and K7∨K_7^{\vee} (two adjacent edges deleted) --- it predicts 6-colorability. A 1971 theorem settled the case where both K7∨K_7^{\vee} and K7=K_7^= are excluded, and in 2025 Norin and Totschnig proved that every graph with no K7∨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 K7=K_7^= minor and of graphs with no K7−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 K7=K_7^= minor is 6-colorable, leaving the K7−K_7^- statement as the surviving level-7 instance. The K7−K_7^- statement implies the K7=K_7^= statement, and the best known bound for graphs with no K7−K_7^- minor is 7-colorability.

Background

A graph HH is a minor of a graph GG if HH can be obtained from a subgraph of GG by contracting edges (merging their endpoints); GG has no HH minor if no such model exists. The chromatic number χ(G)\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 KtK_t minor (KtK_t being the complete graph on tt vertices) is (t−1)(t-1)-colorable. It is equivalent to the Four Color Theorem for t=5t = 5 and was proved for t=6t = 6 by Robertson, Seymour and Thomas (1993); it remains open for all t≥7t \ge 7, and a survey by Seymour (2016) records its status. At the first open level t=7t = 7, even 7-colorability of graphs with no K7K_7 minor is open: Albar and Gonçalves (2018) proved that every graph with no K7K_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 HH on tt vertices, every graph with no HH minor is (t−1)(t-1)-colorable. For H=KtH = K_t this is Hadwiger's conjecture; for any other HH on tt vertices, excluding HH is a weaker restriction than excluding KtK_t (every graph with no KtK_t minor also has no HH minor, since HH is a subgraph of KtK_t), so the statement is weaker than Hadwiger's conjecture at level tt and serves as a stepping stone toward it.

We consider the near-complete 7-vertex graphs. Write K7−K_7^- for K7K_7 with one edge deleted; K7=K_7^= for K7K_7 with two independent edges deleted (a matching of size two); and K7∨K_7^{\vee} for K7K_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 K7∨K_7^{\vee} minor and no K7=K_7^= minor is 6-colorable. Jakobsen also proved in 1971 that every graph with no K7−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 K9−6\mathcal{K}_9^{-6} minor is 8-colorable (where K9−6\mathcal{K}_9^{-6} is the family of all graphs obtained from K9K_9 by deleting six edges) and explicitly lists as open the 6-colorability of graphs excluding each of K7−K_7^-, K7=K_7^= and K7<K_7^< (their notation for K7∨K_7^{\vee}), along with 7-colorability of graphs with no K7K_7 minor, the 8-connectivity of kk-contraction-critical graphs for k≥8k \ge 8, and extensions of their deletion-family sequence. In July 2025, Norin and Totschnig resolved the adjacent-deletion case: every graph with no K7∨K_7^{\vee} minor is 6-colorable. Their proof rests on a new extremal theorem (every 4-connected graph GG with ∣E(G)∣≥4∣V(G)∣−8|E(G)| \ge 4|V(G)| - 8 has a K7∨K_7^{\vee} minor unless GG is isomorphic to K2,2,2,2K_{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 K7=K_7^= fails, since their graphs GnG_n (a universal 4-vertex set joined to a matching on the remaining vertices) are 4-connected with 4∣V∣+⌊∣V∣/2⌋−12≥4∣V∣−84|V| + \lfloor |V|/2 \rfloor - 12 \ge 4|V| - 8 edges and still have no K7=K_7^= minor. They pose Conjecture 19 (every graph with no K7=K_7^= minor is 6-colorable), Conjecture 20 (a possible 5-connected extremal analogue: every 5-connected graph with at least 4∣V∣−94|V| - 9 edges has a K7=K_7^= minor unless it is K6K_6), and Conjecture 21 (every graph with no K7−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 K7=K_7^= minor is 6-colorable, while Conjectures 20 and 21 remain open.

Problem Statement

Let K7−K_7^- denote the complete graph K7K_7 with one edge deleted, and let K7=K_7^= denote K7K_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 K7K_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 K7−K_7^- minor 6-colorable?

This is the stronger of the two statements that Lafferty and Song (2022) recorded as open: K7=K_7^= is a subgraph of K7−K_7^-, so any graph containing a K7−K_7^- minor also contains a K7=K_7^= minor; hence every graph with no K7=K_7^= minor also has no K7−K_7^- minor, and an affirmative answer to (1) settles the 6-colorability of graphs with no K7=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 K7=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 K7−K_7^- minor.

References

  1. Michael Lafferty and Zi-Xia Song (2022), "Every graph with no K9−6\mathcal{K}_9^{-6} minor is 88-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 K7∨K_7^{\vee}-minor is 66-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 88-contraction-critical graphs with no K7K_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 K7−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 K7K_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 K6K_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 K9=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 HH-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 K7=K_7^= minor is 66-colorable", arXiv:2609.17760, DOI 10.48550/arXiv.2609.17760, https://arxiv.org/abs/2609.17760