**November 7, BGW, Bordeaux**

Marcin Wrochna

[$\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

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.

**[$\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$]**

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.:**(= graphs with no [$C_4$] subgraph)*all square-free graphs*- Delhommé & Sauer (2002):
*all square-free graphs, if we only consider [$G,H$] containing triangles.*

**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:**

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:

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]$].

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.

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.

[$\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)]$].

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) $]

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

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

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)$].

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}$].

- [$ \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$].

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:

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:

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.

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$].

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$]** _{□}

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?

- [$\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).

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?

/