Weak pentagon problem

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A cubic graph is a finite simple $3$-regular graph; its girth is the length of a shortest cycle. For $j\ge2$, the projective cube $PQ_j$ is the quotient of the $(j+1)$-dimensional cube (binary strings, adjacent when differing in one coordinate) by identification of antipodal strings. Thus $PQ_4$ is the Clebsch graph. A homomorphism sends adjacent vertices to adjacent vertices. A cut-continuous edge map $f:E(G)\to E(H)$ has the property that $f^{-1}(\delta_H(X))$ is a cut of $G$ for every vertex subset $X$ of $H$.

Statement recorded in the supplied source.

Does every triangle-free cubic graph admit an edge coloring with five colors such that deleting any one color class leaves a bipartite graph? Equivalently, does it have a homomorphism to $PQ_4$, or a cut-continuous map to $C_5$? Also determine the largest integer $k\ge1$ for which there is $g_k$ such that every cubic graph of girth at least $g_k$ maps homomorphically to $PQ_{2k}$. The latter condition is equivalent to an edge coloring with $2k+1$ colors whose individual color-class complements are bipartite, or to a cut-continuous map to $C_{2k+1}$. These edge colorings are not required to be proper. [S2]

Short English statement

Can five color classes each meet every odd cycle in a triangle-free cubic graph, and how far can the analogous high-girth projective-cube statement be extended?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3209 (OPG-434). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Weak pentagon problem, original node 434, statement and mathematical discussion. https://www.openproblemgarden.org/op/weak_pentagon_problem.