Antichains in the Cycle-Continuous Order

A cycle in a graph is a subgraph with each vertex of even degree. A map f : E(G) -> E(H) is cycle-continuous if the preimage of any cycle is a cycle. We write G > H if there is a cycle-continuous map from G to H. It is easy to see that this order is reflexive and transitive.  For example, if A_k is the graph with 2 vertices and k parallel edges, then A_3 < A_5 < A_7 < ... is an infinite chain.

To my knowledge, Matt DeVos introduced this order (see The Petersen coloring conjecture). Apparently little is known about it. DeVos asks the following:

Question: Does there exist an infinite antichain in the cycle-continuous order?

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA. (with thanks to Matt DeVos)

Send comments to

December 2003