Your browser **doesn't support the features required** by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use a decent browser.

Masarykova univerzita

Brno, Česká Republika

Hadwiger's Conjecture

Conjecture (Hadwiger – 1943)

Each graph without a clique minor of size $k\in\mathbb{N}$ can be coloured with $k-1$ colours.

Restrict to subclasses of graphs

- Hadwiger’s Conjecture holds for line graphs.
- Hadwiger’s Conjecture holds for claw-free graphs

with independence number at least 3.

Bound the size of colour classes

Conjecture (Seymour)

Let $G$ be a graph with $\alpha(G) \leq 2$, then $G$ contains a $K_k$-minor with $k := \lceil\frac{|V(G)|}{2}\rceil$.
Furthermore, the $K_k$-certificate can be chosen such that each branch sets consists of one or two vertices.

Bound the number of colouring

↪ this talk

Definition

A *$k$-colouring* of a graph $G$ with $k\in\mathbb{N}$ is a partition $\mathcal{C}$ of the vertex set $V(G)$ into $k'\leq k$ non-empty sets $A_1,\dots,A_{k'}$.

Definition

A graph $G$ is *uniquely $k$-colourable* if there exists only one proper $k$-colouring (partition) of $G$ with $k\in\mathbb{N}$.

Definition

(Kempe-coloured graph)

(Kempe-coloured graph)

A graph that satisfy: For any two distinct colour classes $A,B\in\mathcal{C}$, the subgraph of $G$ induced by $A\cup B$ is connected.

??

Can we merge vertices

such that $T$ is still a transversal?

such that $T$ is still a transversal?

Definition

$G$ has a *rooted $H$-certificate* if and only if:

- it has a
*family $c=(V_t)_{t\in V(H)}$*of connected disjoint subsets of $V(G)$, - there is a
*connecting edge*between $V_s$ and $V_t$ for all $st\in E(H)$, and - $V(H)\subseteq V(G)$ and
*$t\in V_t$*for all $t\in V(H)$.

Conjecture (Kriesell – 2017)

For every transversal $T$ of every Kempe colouring of a graph $G$ there exists a *rooted $K_T$-certificate* in $G$.

True for $|T| \leq 4$ by a result of Fabila-Monroy and Wood.

Theorem (Kriesell, M. – 2019)

True for *line graphs*.

Theorem (Kriesell, M. – 2020+)

For every transversal $T$ of every $k$-colouring of a graph $G$ with *$k\leq 4$* such that all 2-coloured paths between $T$ exist,

there exists a*rooted $K_T$-certificate* in $G$.

there exists a

Moreover: True for $k=5$ if $T$ induces a connected subgraph in $G$.

Theorem (Kriesell, M. – 2020+)

??

Does each graph $G$ and $X\subseteq V(G)$ with $X$ is $k$-connected in $G$ *has a $k$-connected minor* in $G$ that “contains $X$”?

Definition

The vertex subset $S\subseteq V(G)$ is an *$X$-separator* if at least two components of $G-S$ contain a vertex from $X$.

Definition

A subset $X\subseteq V(G)$ is *$k$-connected in $G$* if $|X|\geq k+1$ and no $X$-separator $S$ with $|S| < k$ exists.

Definition

$G$ has a rooted $H$-certificate *half-rooted $H$-certificate rooted at $T\subseteq V(G)$* if

and only if:

and only if:

- it has a
family $c=(V_t)_{t\in V(H)}$ of connected disjoint subsets of $V(G)$, - there is a
connecting edge between $V_s$ and $V_t$ for all $st\in E(H)$, and - $V(H)\subseteq V(G)$
*$T\subseteq V(H)$*and$t\in V_t$ for all $t\in V(H)$*$t\in T$*.

Theorem (Böhme, Harant, Kriesell, M., Schmidt – 2020+)

Let $k\in \{1,2,3,4\}$, $G$ be a graph, and $X\subseteq V(G)$ such that $X$ is $k$-connected in $G$.

- $G$ contains a $k$-connected minor half-rooted at $X$.
- If $k\leq 3$, then $G$ has even a $k$-connected topological minor half-rooted at $X$.

Moreover: Best possible.