On inverse powers of graphs and topological implications of Hedetniemi's conjecture

Abstract

We consider a natural graph operation ${\Omega }_k$ that is a certain inverse (formally: the right adjoint) to taking the k-th power of a graph. We show that it preserves the topology (the ${\mathbb{Z}}_2$-homotopy type) of the box complex, a basic tool in topological combinatorics. Moreover, we prove that the box complex of a graph G admits a ${\mathbb{Z}}_2$-map (an equivariant, continuous map) to the box complex of a graph H if and only if the graph ${\Omega }_k(G)$ admits a homomorphism to H, for high enough k. This allows to show that if Hedetniemi's conjecture on the chromatic number of graph products were true for n-colorings, then the following analogous conjecture in topology would also also true: If X,Y are ${\mathbb{Z}}_2$-spaces (finite ${\mathbb{Z}}_2$-simplicial complexes) such that X x Y admits a ${\mathbb{Z}}_2$-map to the (n-2)-dimensional sphere, then X or Y itself admits such a map. We discuss this and other implications, arguing the importance of the topological conjecture.

References in corpus (2)

• On topological relaxations of chromatic conjectures
• Square-free graphs are multiplicative

Cited by in corpus (3)

• Topology and adjunction in promise constraint satisfaction
• Hom complexes of graphs whose codomains are square-free
• A topological version of Hedetniemi's conjecture for equivariant spaces