![](/files/happy5.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
This conjecture has several reformulations: the conclusion of the conjecture can be replaced by either of the following:
- \item
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ C_5 $](/files/tex/8771f2843d03a080727144559cbb11498a350756.png)
For the latter variant, few definitions are in place. A cut-continuous mapping from a graph~ to a graph~
is a mapping
such that the preimage of every cut in~
is a cut in~
. Here, by a cut in~
we mean the edge-set of a spanning bipartite subgraph of~
---less succinctly, it is the set of all edges leaving some subset of vertices of~
.
Cut-continuous mappings are closely related with graph homomorphisms (see [DNR], [S]). In particular, every homomorphism from~ to~
naturally induces a cut-continuous mapping from~
to~
; 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 -dimensional projective cube, denoted
, is the simple graph obtained from the
-dimensional cube~
by identifying pairs of antipodal vertices (vertices that differ in all coordinates). Note that
is the Clebsch graph.
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ PQ_{2k} $](/files/tex/1ac88966577443b3a9d1a3b7131bd1b406b9b19a.png)
Again, the question has several reformulations due to the following simple proposition.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
- \item There exists a coloring of~
![$ E(G) $](/files/tex/4b556e49b77160d4c8a0131e0efdfefd52dda2bb.png)
![$ 2k+1 $](/files/tex/2642e9bd0dbf7ce13ccc3ecdc069c9c955335fb6.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ PQ_{2k} $](/files/tex/1ac88966577443b3a9d1a3b7131bd1b406b9b19a.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ C_{2k+1} $](/files/tex/f20c34c1abcdfc50a63f8c5920f0ddb51a9f7cae.png)
There are high-girth cubic graphs with the largest cut of size less then . Such graphs do not admit a homomorphism to
for any
, so there is indeed some largest integer~
in the above question. To bound this largest~
from below, recall that every cubic graph maps homomorphically to
. Moreover, it is known [DS] that cubic graphs of girth at least 17 admit a homomorphism to
(the Clebsch graph). This shows
(and also provides a support for the main conjecture).
Bibliography
[DNR] Matt DeVos, Jaroslav Nesetril and Andre Raspaud: On edge-maps whose inverse preserves flows and tensions, \MRref{MR2279171}
*[DS] Matt Devos, Robert Samal: \arXiv[High Girth Cubic Graphs Map to the Clebsch Graph}{math.CO/0602580}
[S] Robert Samal, On XY mappings, PhD thesis, Charles University 2006, tech. report
* indicates original appearance(s) of problem.