# On a recolouring version of Hadwiger's conjecture

Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne, Jonathan Narboni

<figure><img src="image_1.png" /></figure>

## To cite this version:

Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne, Jonathan Narboni. On a recolouring version of Hadwiger's conjecture. 2021. hal-04097535

HAL Id: hal-04097535

https://hal.science/hal-04097535

Preprint submitted on 15 May 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On a recolouring version of Hadwiger's conjecture*

Marthe Bonamy<fnref n="1" />, Marc Heinrich<fnref n="2" />, Clément Legrand-Duchesne<fnref n="3" />, and Jonathan Narboni<fnref n="1" />

March 22, 2021

## Abstract

We prove that for any $\varepsilon > 0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(\frac{3}{2} - \varepsilon)t$-colouring that is “frozen” with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.

## 1 Introduction

In an attempt to prove the Four Colour Theorem in 1879, Kempe [Kem79] introduced an elementary operation on the colourings<fnref n="1" /> of a graph that became known as a Kempe change. Given a *k*-colouring $\alpha$ of a graph $G$, a *Kempe chain* is a maximal bichromatic component<fnref n="2" />. A *Kempe change* in $\alpha$ corresponds to swapping the two colours of a Kempe chain so as to obtain another *k*-colouring. Two *k*-colourings are *Kempe equivalent* if one can be obtained from the other through a series of Kempe changes.

The study of Kempe changes has a vast history, see e.g. [Moh06] for a comprehensive overview or [BBFJ19] for a recent result on general graphs. We refer the curious reader to the relevant chapter of a 2013 survey by Cereceda [vdH13]. Kempe equivalence falls within the wider setting of combinatorial reconfiguration, which [vdH13] is also an excellent introduction to. Perhaps surprisingly, Kempe equivalence has direct applications in approximate counting and applications in statistical physics (see e.g. [Sok00, MS09] for nice overviews). Closer to graph theory, Kempe equivalence can be studied with a goal of obtaining a random colouring by applying random walks and rapidly mixing Markov chains, see e.g. [Vig00].

Kempe changes were introduced as a mere tool, and are decisive in the proof of Vizing's edge colouring theorem [Viz64]. However, the equivalence class they define on the set of *k*-colourings is itself highly interesting. In which cases is there a single equivalence class? In which cases does every equivalence class contain a colouring that uses the minimum number of colours? Vizing conjectured in 1965 [Viz68] that the second scenario should be true in every line graph, no matter the choice of *k*. Despite partial results [Asr09, AC16], this conjecture remains wildly open.

<footnote n="1">¹CNRS, LaBRI, Université de Bordeaux, Bordeaux, France.</footnote>

<footnote n="2">²University of Leeds, United Kingdom.</footnote>

<footnote n="3">³Univ Rennes, F-35000 Rennes, France.</footnote>

<footnote>*The authors are supported by ANR project GrR (ANR-18-CE40-0032).</footnote>

<footnote n="1">¹Throughout this paper, all colourings are proper, i.e. no two vertices with the same colour are adjacent.</footnote>

<footnote n="2">²If a vertex of $G$ is coloured 1 and has no neighbour coloured 2 in $\alpha$, then it forms a Kempe chain of size 1.</footnote>
In the setting of planar graphs, Meyniel proved in 1977 [Mey78] that all 5-colourings form a unique Kempe equivalence class. The result was then extended to all $K_5$-minor-free graphs in 1979 by Las Vergnas and Meyniel [LVM81]. They conjectured the following, which can be seen as a reconfiguration counterpoint to Hadwiger's conjecture, though it neither implies it nor is implied by it.

**Conjecture 1.1 (Conjecture A in [LVM81]).** For every $t$, all the $t$-colourings of a graph with no $K_t$-minor form a single equivalence class.

They also proposed a related conjecture that is weaker assuming Hadwiger's conjecture holds.

**Conjecture 1.2 (Conjecture A' in [LVM81]).** For every $t$ and every graph with no $K_t$-minor, every equivalence class of $t$-colourings contains some $(t-1)$-colouring.

Here, we disprove both Conjectures 1.1 and 1.2, as follows.

**Theorem 1.3.** For every $\varepsilon > 0$ and for any large enough $t$, there is a graph with no $K_t$-minor, whose $(\frac{3}{2} - \varepsilon)t$-colourings are not all Kempe equivalent.

In fact, we prove that for every $\varepsilon > 0$ and for any large enough $t$, there is a graph $G$ that does not admit a $K_t$-minor but admits a $(\frac{3}{2} - \varepsilon)t$-colouring that is *frozen*; Any pair of colours induce a connected component, so that no Kempe change can modify the colour partition. To obtain Theorem 1.3, we then argue that the graph admits a colouring with a different colour partition. The notion of frozen $k$-colouring is related to the notion of quasi-$K_p$-minor, introduced in [LVM81]. A graph $G$ admits a $K_p$-minor if it admits $p$ non-empty, pairwise disjoint and connected bags $B_1, \dots, B_p \subset V(G)$ such that for any $i \neq j$, there is an edge between some vertex in $B_i$ and some vertex in $B_j$. For the notion of quasi-$K_p$-minor, we drop the restriction that each $B_i$ should induce a connected subgraph of $G$, and replace it with the condition that for any $i \neq j$, the set $B_i \cup B_j$ induces a connected subgraph of $G$. If the graph $G$ admits a frozen $p$-colouring, then it trivially admits a quasi-$K_p$-minor$^3$, while the converse may not be true. If all $p$-colourings of a graph form a single equivalence class, then either there is no frozen $p$-colouring or there is a unique $p$-colouring of the graph up to colour permutation. The latter situation in a graph with no $K_p$-minor would disprove Hadwiger's conjecture, so Las Vergnas and Meyniel conjectured that there is no frozen $p$-colouring in that case. Namely, they conjectured the following.

**Conjecture 1.4 (Conjecture C in [LVM81]).** For any $t$, any graph that admits a quasi-$K_t$-minor admits a $K_t$-minor.

Conjecture 1.4 is known to hold for $t \le 8$ [Jør94]. As discussed above, we strongly disprove Conjecture 1.4 for large $t$. It is unclear how large $t$ needs to be for a counter-example.

**Theorem 1.5.** For every $\varepsilon > 0$ and for any large enough $t$, there is a graph $G$ that admits a quasi-$K_t$-minor but does not admit a $K(\frac{2}{3}+\varepsilon)t$-minor.

Trivially, every graph that admits a quasi-$K_{2t}$-minor admits a $K_t$-minor. We leave the following two open questions, noting that $\frac{2}{3} \ge c \ge \frac{1}{2}$ and $c' \ge \frac{3}{2}$.

**Question 1.6.** What is the infimum $c$ such that for any large enough $t$, there is a graph $G$ that admits a quasi-$K_t$-minor but no $K_{ct}$-minor?

**Question 1.7.** Is there a constant $c'$ such that for every $t$, all the $c' \cdot t$-colourings of a graph with no $K_t$-minor form a single equivalence class?

<footnote n="3">³One bag for each colour class.</footnote>
## 2 Construction

Let $n \in \mathbb{N}$ and let $\eta > 0$. We build a random graph $G_n$ on vertex set $\{a_1, \dots, a_n, b_1, \dots, b_n\}$: for every $i \neq j$ independently, we select one pair uniformly at random among $\{(a_i, a_j), (a_i, b_j), (b_i, a_j), (b_i, b_j)\}$ and add the three other pairs as edges to the graph $G_n$.

Note that the sets $\{a_i, b_i\}_{1 \le i \le n}$ form a quasi-$K_n$-minor, as for every $i \neq j$, the set $\{a_i, b_i, a_j, b_j\}$ induces a path on four vertices in $G_n$, hence is connected.

Our goal is to argue that if $n$ is sufficiently large then with high probability the graph $G_n$ does not admit any $K_{(\frac{2}{3}+\eta)n}$-minor. This will yield Theorem 1.5. To additionally obtain Theorem 1.3, we need to argue that with high probability, $G_n$ admits an $n$-colouring with a different colour partition than the natural one, where the colour classes are of the form $\{a_i, b_i\}$. Informally, we can observe that each of $\{a_1, \dots, a_n\}$ and $\{b_1, \dots, b_n\}$ induces a graph behaving like a graph in $G_{n, \frac{3}{4}}$ (i.e. each edge exists with probability $\frac{3}{4}$) though the two processes are not independent. This argument indicates that $\chi(G_n) = O(\frac{n}{\log n})$, but we prefer a simpler, more pedestrian approach.

Assume that for some $i, j, k, \ell$, none of the edges $a_ib_j, a_jb_k, a_kb_\ell$ and $a_\ell b_i$ exist. Then the graph $G_n$ admits an $n$-colouring $\alpha$ where $\alpha(a_p) = \alpha(b_p) = p$ for every $p \notin \{i, j, k, \ell\}$ and $\alpha(a_i) = \alpha(b_j) = i$, $\alpha(a_j) = \alpha(b_k) = j$, $\alpha(a_k) = \alpha(b_\ell) = k$ and $\alpha(a_\ell) = \alpha(b_i) = \ell$ (see Figure 1). Since every quadruple $(i, j, k, \ell)$ has a positive and constant probability of satisfying this property, $G_n$ contains such a quadruple with overwhelmingly high probability when $n$ is large.

<figure><img src="image_3.png" /><figcaption>Figure 1: A different $n$-colouring given an appropriate quadruple.</figcaption></figure>

We are now ready to prove that the probability that $G_n$ admits a $K_{(\frac{2}{3}+\eta)n}$-minor tends to 0 as $n$ grows to infinity. We consider three types of $K_p$-minors in $G$, depending on the size of the bags involved. If every bag is of size 1, we say that it is a *simple* $K_p$-minor – in fact, it is a subgraph. If every bag is of size 2, we say it is a *double* $K_p$-minor. If every bag is of size at least 3, we say it is a *triple* $K_p$-minor. We prove three claims, as follows.

**Claim 2.1.** For any $\varepsilon > 0$, $\mathbb{P}(G_n \text{ contains a simple } K_{\varepsilon n}\text{-minor}) \to 0 \text{ as } n \to \infty$.

**Claim 2.2.** For any $\varepsilon > 0$, $\mathbb{P}(G_n \text{ contains a double } K_{\varepsilon n}\text{-minor}) \to 0 \text{ as } n \to \infty$.
**Claim 2.3.** $G_n$ does not contain a triple $K_{\frac{2}{3}n+1}$-minor.

Claims 2.1, 2.2 and 2.3 are proved in Sections 2.1, 2.2 and 2.3, respectively. If a graph admits a $K_p$-minor, then in particular it admits a simple $K_a$-minor, a double $K_b$-minor and a triple $K_c$-minor such that $a + b + c \ge p$. Combining Claims 2.1, 2.2 and 2.3, we derive the desired conclusion.

**2.1 No large simple minor**

*Proof of Claim 2.1.* Let $S$ be a subset of $k$ vertices of $G_n$. The probability that $S$ induces a clique in $G_n$ is at most $(\frac{3}{4})^{\binom{k}{2}}$. Indeed, if $\{a_i, b_i\} \subseteq S$ for some $i$, then the probability is 0. Otherwise, $|S \cap \{a_i, b_i\}| \le 1$ for every $i$, so we have $G[S] \in \mathcal{G}_{k, \frac{3}{4}}$, i.e. edges exist independently with probability $\frac{3}{4}$. Therefore, the probability that $S$ induces a clique is $(\frac{3}{4})^{\binom{k}{2}}$.

By union-bound, the probability that some subset on $k$ vertices induces a clique is at most $\binom{2n}{k} \cdot (\frac{3}{4})^{\binom{k}{2}}$. For any $\varepsilon > 0$, we note that $\binom{2n}{\varepsilon n} \le 2^{2n}$. Therefore, the probability that $G_n$ contains a simple $K_{\varepsilon n}$-minor is at most $2^{2n} \cdot (\frac{3}{4})^{\binom{\varepsilon n}{2}}$, which tends to 0 as $n$ grows to infinity. ∎

**2.2 No large double minor**

*Proof of Claim 2.2.* Let $S'$ be a subset of $k$ pairwise disjoint pairs of vertices in $G_n$ such that for every $i$, at most one of $\{a_i, b_i\}$ is involved in $S'$.

We consider the probability that $G_n/S'$ induces a clique, where $G_n/S'$ is defined as the graph obtained from $G_n$ by considering only vertices involved in some pair of $S'$ and identifying the vertices in each pair.

We consider two distinct pairs $(x_1, y_1), (x_2, y_2)$ of $S'$. Without loss of generality, $\{x_1, x_2, y_1, y_2\} = \{a_i, a_j, a_k, a_\ell\}$ for some $i, j, k, \ell$. The probability that there is an edge between $\{x_1, y_1\}$ and $\{x_2, y_2\}$ is $1 - (\frac{1}{4})^4$. In other words, $\mathbb{P}(E((x_1, y_1), (x_2, y_2)) = \emptyset) = (\frac{1}{4})^4$ and since at most one of $\{a_i, b_i\}$ is involved in $S'$ for all $i$, all such events are mutually independent. Therefore, the probability that $S'$ yields a quasi-$K_{|S'|}$-minor is $(1 - (\frac{1}{4})^4)^{\binom{|S'|}{2}}$.

For any $\varepsilon' > 0$, the number of candidates for $S'$ is at most $\binom{2n}{2\varepsilon'n}$ (the number of choices for a ground set of $2\varepsilon'n$ vertices) times $(2\varepsilon'n)!$ (a rough upper bound on the number of ways to pair them). Note that $\binom{2n}{2\varepsilon'n} \cdot (2\varepsilon'n)! \le (2n)^{2\varepsilon'n}$. We derive that the probability that there is a set $S'$ of size $\varepsilon'n$ such that $G_n/S' = K_{|S'|}$ is at most $(2n)^{2\varepsilon'n} \cdot (1 - (\frac{1}{4})^4)^{\binom{\varepsilon'n}{2}}$, which tends to 0 as $n$ grows large.

Consider a double $K_k$-minor $S$ of $G_n$. Note that no pair in $S$ is equal to $\{a_i, b_i\}$ (for any $i$), as every bag induces a connected subgraph in $G_n$. We build greedily a maximal subset $S' \subseteq S$ such that $S'$ involves at most one vertex out of every set of type $\{a_i, b_i\}$. Note that $|S'| \ge \frac{|S|}{3}$. By taking $\varepsilon' = \frac{\varepsilon}{3}$ in the above analysis, we obtain that the probability that there is a set $S$ of $\varepsilon n$ pairs that induces a quasi-$K_{|S|}$-minor tends to 0 as $n$ grows large. ∎

**2.3 No large triple minor**

*Proof of Claim 2.3.* The graph $G_n$ has $2n$ vertices, and a triple $K_k$-minor involves at least $3k$ vertices. It follows that if $G_n$ contains a triple $K_k$-minor then $k \le \frac{2n}{3}$. ∎
# Acknowledgements

The authors thank Vincent Delecroix for helpful discussions.

# References

[AC16] Armen S. Asratian and Carl Johan Casselgren. Solution of Vizing's problem on inter-changes for the case of graphs with maximum degree 4 and related results. *Journal of Graph Theory*, 82(4):350-373, 2016.

[Asr09] Armen S. Asratian. A note on transformations of edge colorings of bipartite graphs. *Journal of Combinatorial Theory, Series B*, 99(5):814-818, 2009.

[BBFJ19] Marthe Bonamy, Nicolas Bousquet, Carl Feghali, and Matthew Johnson. On a conjecture of Mohar concerning Kempe equivalence of regular graphs. *Journal of Combinatorial Theory, Series B*, 135:179-199, 2019.

[Jør94] Leif K. Jørgensen. Contractions to K8. *Journal of Graph Theory*, 18(5):431-448, 1994.

[Kem79] Alfred B. Kempe. On the geographical problem of the four colours. *American journal of mathematics*, 2(3):193-200, 1879.

[LVM81] Michel Las Vergnas and Henri Meyniel. Kempe classes and the Hadwiger conjecture. *Journal of Combinatorial Theory, Series B*, 31(1):95-104, 1981.

[Mey78] Henry Meyniel. Les 5-colorations d'un graphe planaire forment une classe de com-mutation unique. *J. Comb. Theory, Ser. B*, 24:251-257, 1978.

[Moh06] Bojan Mohar. Kempe equivalence of colorings. In *Graph Theory in Paris*, pages 287-297. Springer, 2006.

[MS09] Bojan Mohar and Jesús Salas. A new Kempe invariant and the (non)-ergodicity of the Wang-Swendsen-Kotecký algorithm. *Journal of Physics A: Mathematical and Theoretical*, 42(22):225204, 2009.

[Sok00] Alan D. Sokal. A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models. arXiv preprint cond-mat/0004231, 2000.

[vdH13] Jan van den Heuvel. The complexity of change. *Surveys in combinatorics*, 409(2013):127-160, 2013.

[Vig00] Eric Vigoda. Improved bounds for sampling colorings. *Journal of Mathematical Physics*, 41(3):1555-1569, 2000.

[Viz64] Vadim G. Vizing. On an estimate of the chromatic class of a p-graph. *Discret Analiz*, 3:25-30, 1964.

[Viz68] Vadim G. Vizing. Some unsolved problems in graph theory. *Russian Mathematical Surveys*, 23(6):125, 1968.