Graph Theory » Coloring » Nowhere-zero flows

Antichains in the cycle continuous order ★★

Author(s): DeVos

If $ G $,$ H $ are graphs, a function $ f : E(G) \rightarrow E(H) $ is called cycle-continuous if the pre-image of every element of the (binary) cycle space of $ H $ is a member of the cycle space of $ G $.

Problem   Does there exist an infinite set of graphs $ \{G_1,G_2,\ldots \} $ so that there is no cycle continuous mapping between $ G_i $ and $ G_j $ whenever $ i \neq j $ ?

Keywords: antichain; cycle; poset

Posted by mdevos
updated May 12th, 2007
add new comment
Graph Theory » Topological G.T. » Crossing numbers

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture   Let $ G $ be the disjoint union of the graphs $ G_1 $ and $ G_2 $ and let $ \Sigma $ be a surface. Is it true that every optimal drawing of $ G $ on $ \Sigma $ has the property that $ G_1 $ and $ G_2 $ are disjoint?

Keywords: crossing number; surface

Posted by mdevos
updated September 30th, 2007
1 comment
Geometry » Polytopes

Fat 4-polytopes ★★★

Author(s): Eppstein; Kuperberg; Ziegler

The fatness of a 4-polytope $ P $ is defined to be $ (f_1 + f_2)/(f_0 + f_3) $ where $ f_i $ is the number of faces of $ P $ of dimension $ i $.

Question   Does there exist a fixed constant $ c $ so that every convex 4-polytope has fatness at most $ c $?

Keywords: f-vector; polytope

Posted by mdevos
updated May 12th, 2007
add new comment