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
f
: 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
p
on the class of finite graphs. Namely, G
p
H if there
exists a cycle-continuous mapping from G to H. The goal of
this talk is to study this and other related quasi-orders. In
particular, we establish a number of connections between
structural properties of these quasi-orders and traditional
flow/coloring problems.
∼Andre Raspaud教授演講摘要∼