Every graph with no K 7 ∨ K_{7}^{\vee} -minor is 6 6 -colorable
Sergey Norin and Agnès Totschnig · 2025
Read Every graph with no K 7 ∨ K_{7}^{\vee} -minor is 6 6 -colorable by Sergey Norin and Agnès Totschnig (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03244.txt.
Introduction
Sergey Norin and Agnès Totschnig prove a coloring result in graph theory, in a paper published in 2025. The result concerns a graph built from the complete graph on seven points by removing two edges that share an end. A graph with no copy of that pattern hidden inside it, in the minor sense, is the subject.
Catalog record
| CREATOR | Sergey Norin and Agnès Totschnig |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-03244
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Every graph with no K 7 ∨ K_{7}^{\vee} -minor is 6 6 -colorable Thanks: SN was partially supported by NSERC Discovery Grant. AT was supported by a McCall MacBain Scholarship and partially by FRQNT Grant 332481. Sergey Norin and Agnès Totschnig Abstract . Let K 7 ∨ K_{7}^{\vee} denote the graph obtained from the complete graph on seven vertices by deleting two edges with a common end. Motivated by Hadwiger’s conjecture, we prove that every graph with no K 7 ∨ K_{7}^{\vee} -minor is 6 6 -colorable. 1. Introduction In 1943 Hadwiger made the following famous conjecture. Conjecture 1 (Hadwiger’s conjecture [ Had43 ] ) . For every integer t\geq 1 , every graph with no K_{t} minor is (t-1) -colorable. We refer the reader to a comprehensive survey by Seymour [ Sey16 ] of progress towards the conjecture, and only give a brief overview of the results closest to our investigation. Hadwiger [ Had43 ] and Dirac [ Dir52 ] independently showed that Conjecture 1 holds for t\leq 4 . Wagner [ Wag37 ] proved that for t=5 Hadwiger’s conjecture is equivalent to the Four Color Theorem, which was subsequently proved by Appel and Haken [ AH77 , AHK77 ] . Robertson, Seymour and Thomas [ RST93 ] proved Hadwiger’s conjecture for t=6 , also by reducing it to the Four Color Theorem. In this paper we are concerned with the next open case: t=7 . Settling the conjecture in this case appears to be extremely challenging. Albar and Gonçalves [ AG18 ] proved that every graph with no K_{7} minor is 8 -colorable, but even the question whether every such graph is 7 -colorable is open. (Rolek, Song and Thomas discuss properties of minor minimal non- 7 -colorable graphs with no K_{7} -minor in [ RST23 ] .) In another direction, several authors explored minors that are guaranteed to be present in every non- 6 -colorable graph. The following two theorems of Jakobsen [ Jak71 ] and of Kawarabayashi and Toft [ KT05 ] , in particular, inspired our results. Stating Jakobsen’s result requires the following additional notation. For t\geq 4 , let K^{\vee}_{t} denote the graph obtained from K_{t} by deleting two edges with a common end, and let K^{=}_{t} denote the graph obtained from K_{t} by deleting a two-edge matching. Thus every graph obtained from K_{t} by deleting two edges is isomorphic to K^{\vee}_{t} or K^{=}_{t} . Theorem 2 (Jakobsen [ Jak71 ] ) . Every graph with no K_{7}^{\vee} -minor and no K^{=}_{7} -minor is 6 -colorable. Theorem 3 (Kawarabayashi and Toft [ KT05 ] ) . Every graph with no K_{7} -minor and no K_{4,4} -minor is 6 -colorable. Our main theorem strengthens Jakobsen’s result, showing that excluding K^{=}_{7} is not necessary. Theorem 4 . Every graph with no K_{7}^{\vee} -minor is 6 -colorable. The proof of 4 uses the same overall strategy as the proofs of Theorems 2 and 3 , which is also deployed to some extent in the proofs of the Four Color Theorem and Hadwiger’s conjecture for t=6 . However, we have to substantially extend the toolkit used in the proofs of these earlier results. We hope that our techniques could be further applied to closer approach Hadwiger’s conjecture for small values of t . First, we restrict our attention to 7 -contraction-critical graphs, i.e. graphs G such that \chi(G)=7 and \chi(G^{\prime})<7 for every proper minor G^{\prime} of G . Second, we determine the maximum number of edges in G , as a function of the number of vertices. In the proof of 3 , the corresponding part of the argument uses the following result of Jørgensen. Theorem 5 (Jørgensen [ Jø94 ] ) . Every 4 -connected graph G with |E(G)|\geq 4|V(G)|-7 has a K_{4,4} -minor, unless G\simeq K_{7} . The main technical part in the proof of 4 is establishing the following analogue of 5 in our setting. Theorem 6 . Every 4 -connected graph G with |E(G)|\geq 4|V(G)|-8 has a K_{7}^{\vee} -minor, unless G\simeq K_{2,2,2,2} . In Section 2 , as a step towards the proof of 6 , we obtain extremal results guaranteeing the existence of certain “rooted” minors, using and refining theorems of Robertson, Seymour and Thomas [ RST93 ] and Jørgensen [ Jø94 ] . In Section 3 we prove 6 . In Section 4 we implement the remainder of the strategy and complete the proof of 4 . The brief outline of the argument is as follows. By 6 , we can conclude that G contains many degree seven vertices. The neighborhood of every degree seven vertex contains a clique of size five, except for one case, which we dismiss using a recent theorem of Kriesell and Mohr [ KM19 ] . The resulting cliques can than be connected to obtain the required minor. This last part closely follows the argument in [ KT05 ] , which is in turn inspired by [ RST93 ] . We conclude with several open questions in Section 5 . Notation We use standard graph theoretical notation. We denote the subgraph of a graph G induced by a set X\subseteq V(G) by G[X] . A separation of a graph G is a pair (A,B) such that A\cup B=V(G) and G[A]\cup G[B]=G , i.e. no edge of G has one end in A-B and the other in B-A . The order of a separation (A,B) is |A\cap B| . A separation (A,B) is non-trivial if A,B\neq V(G) . A k -separation is a separation of order k . We write G\simeq H if the graphs G and H are isomorphic. We denote by N(v) the set of all vertices adjacent to the vertex v in a graph G (where G is understood from context, whenever we use this notation). Let N[v]=N(v)\cup\{v\} . We denote the graph obtained from the complete graph K_{t} by deleting a single edge by K^{-}_{t} . 2. Rooted models Many of the results we use in this paper are best stated in terms of rooted models, which we now define. Let k be a non-negative integer. A k -rooted graph is a (k+1) -tuple (G,v_{1},\ldots,v_{k}) consisting of a graph G and an ordered sequence of pairwise distinct vertices of G . Let (H,u_{1},\ldots,u_{k}) and (G,v_{1},\ldots,v_{k}) be two k -rooted graphs. A (v_{1},\ldots,v_{k}) -rooted (H,u_{1},\ldots,u_{k}) -model in G is a function \alpha assigning to each u\in V(H) a set \alpha(u)\subseteq V(G) such that • \alpha(u)\cap\alpha(u^{\prime})=\emptyset for all u,u^{\prime}\in V(H) , u\neq u^{\prime} , • the subgraph G[\alpha(u)] , which we refer to as a bag of this model , is non-null and connected for every u\in V(H) , • for every uu^{\prime}\in E(H) there exists an edge of G with one end in \alpha(u) and another in \alpha(u^{\prime}) , and • v_{i}\in\alpha(u_{i}) for every i\in[k] . Note that contracting all the bags of the model to single vertices we obtain a minor of G with a subgraph isomorphic to H induced by the vertices resulting from contraction, and, in particular, an edge joining vertices corresponding to v_{i} and v_{j} , whenever u_{i} and u_{j} are adjacent in H . If H and G are graphs X\subseteq V(H),Z\subseteq V(G) with |X|=|Z|=k then a Z -rooted (H,X)