Open Problem Garden

Importance: Medium ✭✭

Author(s):

Subject:	Graph Theory
	» Coloring
	» » Homomorphisms

Keywords:	Clebsch graph
	cut-continuous mapping
	edge-coloring
	homomorphism
	pentagon

Recomm. for undergrads: no

Posted	by:	Robert Samal
	on:	July 13th, 2007

Conjecture If $G$ is a cubic graph not containing a triangle, then it is possible to color the edges of $G$ by five colors, so that the complement of every color class is a bipartite graph.

This conjecture has several reformulations: the conclusion of the conjecture can be replaced by either of the following:

$G$

Clebsch graph

$G$

$C_5$

For the latter variant, few definitions are in place. A cut-continuous mapping from a graph~ $G$ to a graph~ $H$ is a mapping $f : E(G) \to E(H)$ such that the preimage of every cut in~ $H$ is a cut in~ $G$ . Here, by a cut in~ $H$ we mean the edge-set of a spanning bipartite subgraph of~ $H$ ---less succinctly, it is the set of all edges leaving some subset of vertices of~ $H$ .

Cut-continuous mappings are closely related with graph homomorphisms (see [DNR], [S]). In particular, every homomorphism from~ $G$ to~ $H$ naturally induces a cut-continuous mapping from~ $G$ to~ $H$ ; thus, the presented conjecture can be thought of as a weaker version of Nesetril's Pentagon problem.

We mention a generalization of the conjecture, that deals with longer cycles/larger number of colors. The $n$ -dimensional projective cube, denoted $PQ_n$ , is the simple graph obtained from the $(n+1)$ -dimensional cube~ $Q_{n+1}$ by identifying pairs of antipodal vertices (vertices that differ in all coordinates). Note that $PQ_4$ is the Clebsch graph.

Question What is the largest integer $k$ with the property that all cubic graphs of sufficiently high girth have a homomorphism to $PQ_{2k}$ ?

Again, the question has several reformulations due to the following simple proposition.

Proposition For every graph $G$ and nonnegative integer $k$ , the following properties are equivalent.

$E(G)$

$2k+1$

$G$

$PQ_{2k}$

$G$

$C_{2k+1}$

There are high-girth cubic graphs with the largest cut of size less then $0.94\cdot |E|$ . Such graphs do not admit a homomorphism to $PQ_{2k}$ for any $k \ge 8$ , so there is indeed some largest integer~ $k$ in the above question. To bound this largest~ $k$ from below, recall that every cubic graph maps homomorphically to $K_4 = PQ_2$ . Moreover, it is known [DS] that cubic graphs of girth at least 17 admit a homomorphism to $PQ_4$ (the Clebsch graph). This shows $k\ge 2$ (and also provides a support for the main conjecture).