Abstract

The well celebrated four colour theorem claims, with a slight reformulation, that every $K_5$ minor-free graph admits a homomorphism to $K_4$. We consider possible extensions of the four colour theorem from homomorphism point of view. Projective cube of dimension $k$, denoted $PC(k)$, is a graph obtained from hypercube of dimension $k+1$ by identifying antipodal vertices. We introduce several conjectures and questions with respect to homomorphism of planar graphs into projective cubes. Since $PC(2)$ is isomorphic to $K_4$, the first of these questions is the four colour theorem. The general questions we ask, surprisingly, captures many well known theories and conjectures on the theory of vertex coloring, edge coloring, fractional coloring and circular coloring of planar graphs and leads to new theories.



Information: