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.

Rooted Structures in Graphs

BYMAT2020 • Bringing Young Mathematicians Together

Samuel Mohr

December 1st, 2020

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
Reed, Seymour – 2004; Fradkin – 2012:
  • 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
(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?
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$.

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

Theorem (Kriesell, M. – 2020+)
False for all $k\geq 7$.
??
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$-certificatehalf-rooted $H$-certificate rooted at $T\subseteq V(G)$ 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$.
  1. $G$ contains a $k$-connected minor half-rooted at $X$.
  2. If $k\leq 3$, then $G$ has even a $k$-connected topological minor half-rooted at $X$.

Moreover: Best possible.