Antichains in the cycle continuous order
OPG_cycle_continuous_order_infinite_antichain
Source: Open Problem Garden: 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.