Antichains in the cycle continuous order
Status solved high confidence
Šámal (2012, published 2017) answered DeVos's question affirmatively by proving that there exists an infinite set of graphs with no cycle-continuous mapping between any two of them, i.e., an infinite antichain in the cycle-continuous quasi-order. The result is further strengthened to show that every countable poset can be represented by graphs and cycle-continuous mappings.
Cited literature (1)
-
Proves the existence of an infinite antichain in the cycle-continuous mapping quasi-order (answering DeVos–Nešetřil–Raspaud), and shows every countable poset embeds in this order; published in J. Graph Theory 85(1):56–73, 2017.
Reviewer notes. The arXiv preprint was submitted 2012-12-31, well after the OPG posting date of 2007-05-12. The journal version appeared in J. Graph Theory 85(1):56–73 (May 2017), confirmed via DBLP. The problem was originally attributed to DeVos, Nešetřil, and Raspaud; the OPG page credits only DeVos. The DOI for the JGT article was not directly retrieved but the DBLP entry confirms volume/pages.
Discussion
The definition of a cycle-continuous mapping is based on some work of Jaeger, and the most interesting question on this subject is undoubtedly Jaeger's Petersen coloring conjecture . Let us define a relation on the set of all finite graphs with at least one edge by the rule $ G>H $ if there is a cycle-continuous mapping from $ G $ to $ H $ . It is not difficult to verify that $ > $ is a quasi order (reflexive and transitive). In this order, every Eulerian graph dominates every other graph, and every graph with a cut edge is dominated by every other graph. Let $ A_i $ be the graph on two vertices with $ i $ parallel edges. Then $ A_3 < A_5 < A_7 < ... $ with all the inequalities strict, so this sequence is an infinite chain. Very little else seems to be known about this order. In particular, the problem highlighted above - does there exist an infinite antichain? remains open.