### Square-free graphs are multiplicative

#### A topological approach related to Hedetniemi's conjecture

November 7, BGW, Bordeaux
Marcin Wrochna

## Hedetniemi's conjecture (1966)

$\chi(G\times H) = \min(\chi(G),\chi(H))$

Where $G \times H$ is defined as:

•     vertices $= V(G)\times V(H)$
•     $(g_1,h_1) \sim (g_2,h_2)$   whenever   $g_1 g_2 \in E(G)$ and $h_1 h_2 \in E(H)$.

also known as categorical product.

## Graph homomorphism

A graph homomorphism $\mu : G \to H$
is a function $V(G)\to V(H)$
such that       $uv$ is an edge $\implies \mu(u)\mu(v)$ is an edge.

Also called an $H$-coloring of $G$
($k$-coloring = $K_k$-coloring)

We write $G\to H$ if there is any.

## Hedetniemi's conjecture

$\chi(G\times H) = \min(\chi(G),\chi(H))$

equivalently

$G \times H \to K_k\quad\Leftrightarrow\quad G\to K_k\ \mbox{ or }\ H\to K_k$

A graph $K$ is multiplicative if

$G \times H \to K\quad\Leftrightarrow\quad G\to K\ \mbox{ or }\ H\to K$

## Multiplicative graphs

A graph $K$ is multiplicative if        $G \times H \to K\quad\Leftrightarrow\quad G\to K\ \mbox{ or }\ H\to K$

• Hedetniemi's conjecture:   all cliques $K_n$ are multiplicative?
• El-Zahar & Sauer ('85):     $K_3$
• Häggkvist et al. ('88):       all cycles $C_n$
• Tardif (2005):                   circular cliques $K_{p/q}$ with $\frac{p}{q}<4$
• W.:                                  all square-free graphs     (= graphs with no $C_4$ subgraph)
• Delhommé & Sauer (2002):   all square-free graphs, if we only consider $G,H$ containing triangles.

## General idea – graphs as spaces

Every graph gets a corresponding topological space:
a copy of $[0,1]$ for every edge, endpoints glued into vertices.

Every $K$-coloring of $G$ corresponds to a continuous map:

## Walk types

Consider closed walks $C = g_0 g_1 g_2 \dots g_0$ (vertices and edges may repeat) in $G$, based at $g_0$.
We define an equivalence relation:

## Walk types

Consider closed walks $C = g_0 g_1 g_2 \dots g_0$ (vertices and edges may repeat) in $G$, based at $g_0$.
Let the equivalence class (its type) be $[C]$.

## Graphs as spaces

We want the space of $C_1 \times C_2$ to be the product of spaces for $C_1$ and $C_2$ – so, a torus.

## Graphs as spaces

We want the space of $C_1 \times C_2$ to be the product of spaces for $C_1$ and $C_2$ – so, a torus.

## Fundamental group

$\pi(G)$ =

• elements: types $[C]$ of closed walks based at $g_0$
• multiplication: concatenation of walks
• inverse: reverse the walk

Homomorphism Lemma
Let $\mu: G \times H \to K$   and let   $[C]\in \pi(G\times H)$.
Then $[\mu(C)]\in \pi(K)$
and $[\mu(C \cdot D)] = [\mu(C)]\cdot[\mu(D)]$.

## Back to products

Let $[C]\in \pi(G\times H)$.
Then $[C|_G]\in \pi(G)$.

Product Lemma
The mapping $[C] \mapsto ([C|_G], [C|_H])$ is an isomorphism onto its image
$\pi(G\times H) \to \pi(G) \times \pi(H)$

## Example with products

 $([C_G], \varepsilon)$ $(\varepsilon, [C_H])$

## Example with products

 $([C_G], \varepsilon) + (\varepsilon, [C_H])\ =\ ([C_G], [C_H])\ =\ (\varepsilon, [C_H]) + ([C_G], \varepsilon)$

## Using the idea

Let $[C_G] \in \pi(G),\ [C_H] \in \pi(H)$, and $\mu : G\times H \to K$.

$([C_G],\varepsilon)$ is a type that commutes with $(\varepsilon,[C_H])$     in $\pi(G \times H)$ .

Hence     $\mu([C_G],\varepsilon)$ commutes with $\mu(\varepsilon,[C_H])$     in $\pi(K)$.

For square-free $K$, this means winding around the same cycle!
Because for two different cycles, $X \cdot Y \neq Y \cdot X$ in $\pi(K)$.

## Using the idea

Let $[C_G] \in \pi(G),\ [C_H] \in \pi(H)$.

Then if $K$ is square-free:

$\mu([C_G],\varepsilon) = R^{\cdot i}$   and   $\mu(\varepsilon,[C_H]) = R^{\cdot j}$

for some $R \in \pi(K)$ (the root) and $i,j\in \mathbb{Z}$.

## Using the idea

Theorem Let $\mu : G\times H \to K$ for a square-free $K$. Either:
• $\mu([C_G],\varepsilon) = \varepsilon$ for all closed walks in $G$,
• $\mu(\varepsilon,[C_H]) = \varepsilon$ for all closed walks in $H$,
• or $\mu([C]) = \mu([C|_G], \varepsilon) \cdot \mu(\varepsilon, [C|_H]) = R^{\cdot i}$ for all closed walks in $G \times H$.

## Back to reality

Suppose $\mu([C_G],\varepsilon) = \varepsilon$ for all closed walks in $G$. This means:

For any closed walk $g_0 g_1 g_2 \dots g_0$ in $G$ and any $h_0 h_1 \in E(H)$,
the sequence $\mu(g_i, h_{i{\small\mbox{ mod }}2})$ of colors in $K$ looks like this:

## Back to reality

Suppose $\mu([C_G],\varepsilon) = \varepsilon$ for all closed walks in $G$. This means:

For any closed walk $g_0 g_1 g_2 \dots g_0$ in $G$ and any $h_0 h_1 \in E(H)$,
the sequence $\mu(g_i, h_{i{\small\mbox{ mod }}2})$ of colors in $K$ looks like this:

## Recoloring

Let $\mu: G\times H \to K$.
We change colors (values assigned by $\mu$) one by one
to get a $\mu^*$ such that $\mu^*(\cdot, h)$ is as constant as possible for each $h \in H$.

Lemma   Homotopy types essentially don't change when recoloring.

## Recoloring

Let $\mu: G\times H \to K$.
We change colors (values assigned by $\mu$) one by one
to get a $\mu^*$ such that $\mu^*(\cdot, h)$ is as constant as possible for each $h \in H$.

## Recoloring

Assume $\mu([C_G],\varepsilon) = \varepsilon$ for all closed walks $C_G$ in $G$.

Then with recoloring we get $\mu^* : G \times H \to K$
such that $\mu^*(g_1,h) = \mu^*(g_2,h)$     for all $g_1,g_2,h$.

So $\mu^*(g,h) = \gamma(h)$, where $\gamma : H \to K$

Assume $\mu(\varepsilon,[C_H]) = \varepsilon$ for all closed walks $C_H$ in $H$.
Then with recoloring we get   $G \to K$

## Recoloring

Assume $\mu([C]) = R^{\cdot i}$ for all closed walks in $G \times H$, for some common $R \in \pi(K)$.

Then after recoloring, $\mu^*(G\times H) \subseteq R$

$R$ corresponds to a $\delta: C_n \to K$,
so $\mu^* : G\times H \xrightarrow{\quad} C_n \xrightarrow{\ \delta\ } K$

By multiplicativity of cycles, we have
$G \to C_n \to K$   or   $H \to C_n \to K$

Thank you!     Questions?

## The case of circular $K$

• $\pi(K) \simeq \mathbb{Z}$,     the type of a $\mu(C)$ says how many times it winds around $K$.
• Let $\mu: G \times H \to K$.
Let $C_G$, $C_H$ be odd cycles in $G,H$.
$\mu([C_G],\varepsilon) \cdot \mu(\varepsilon,[C_H]) = \mu([C])$ for some $[C]\in\pi(K)$ of odd length.

• Hence $\mu([C_G],\varepsilon)$ winds an odd number of times, for all odd cycles $C_G$
and   $\mu(\varepsilon,[C_H])$ winds an even number of times, for all odd cycles $C_H$ (or vice-versa).

## The case of circular $K$

• Hence $\mu([C_G],\varepsilon)$ winds an odd number of times, for all odd cycles $C_G$.

• If a cycle winds oddly, then there are two antipodal points of the cycle that map to antipodal points of $K$.
• This means every odd cycle in $G$ has a vertex $g$ with $\mu(g,h_0) = \mu(g,h_1)$.
• We give those vertices $g$ this color,
and color the remaining bipartite subgraph with $\mu(g,h_0)$ and $\mu(g,h_1)$, alternatingly.
• Thus $G \to K$

Thank you!     Questions?

/