2006/12/20 by Matt DeVos, Jaroslav Nešetřil, André Raspaud · 1 citation
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Homotopy and Cohomology in Algebraic Topology #Advanced Graph Theory Research #Conjecture #Combinatorics #Mathematics #Antichain #Vertex (graph theory) #Graph #Discrete mathematics #Inverse #Partially ordered set #Geometry
paper · doi:10.1007/978-3-7643-7400-6_10
openalex publication_date 2006/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02
A cycle of a graph G is a set C ⊑ E(G) so that every vertex of the graph (V (G), C) has even degree. If G,H are graphs, we define a map φ: E(G) → E(H) to be cycle-continuous if the pre-image of every cycle of H is a cycle of G. A fascinating conjecture of Jaeger asserts that every bridgeless graph has a cycle-continuous mapping to the Petersen graph. Jaeger showed that if this conjecture is true, then so is the 5-cycle-double-cover conjecture and the Fulkerson conjecture.Cycle continuous maps give rise to a natural quasi-order ≻ on the class of finite graphs. Namely, G ≻ H if there exists a cycle-continuous mapping from G to H. The goal of this paper is to establish some basic structural properties of this (and other related) quasi-orders. For instance, we show that ≻ has antichains of arbitrarily large finite size. It appears to be an interesting question to determine if ≻ has an infinite antichain.