Strong matchings and covers ★★★

Author(s): Aharoni

Let $ H $ be a hypergraph. A strongly maximal matching is a matching $ F \subseteq E(H) $ so that $ |F' \setminus F| \le |F \setminus F'| $ for every matching $ F' $. A strongly minimal cover is a (vertex) cover $ X \subseteq V(H) $ so that $ |X' \setminus X| \ge |X \setminus X'| $ for every cover $ X' $.

Conjecture   If $ H $ is a (possibly infinite) hypergraph in which all edges have size $ \le k $ for some integer $ k $, then $ H $ has a strongly maximal matching and a strongly minimal cover.

Keywords: cover; infinite graph; matching

Decomposing eulerian graphs ★★★


Conjecture   If $ G $ is a 6-edge-connected Eulerian graph and $ P $ is a 2-transition system for $ G $, then $ (G,P) $ has a compaible decomposition.

Keywords: cover; cycle; Eulerian

Faithful cycle covers ★★★

Author(s): Seymour

Conjecture   If $ G = (V,E) $ is a graph, $ p : E \rightarrow {\mathbb Z} $ is admissable, and $ p(e) $ is even for every $ e \in E(G) $, then $ (G,p) $ has a faithful cover.

Keywords: cover; cycle

(m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

Conjecture   Every bridgeless graph has a (5,2)-cycle-cover.

Keywords: cover; cycle

The circular embedding conjecture ★★★

Author(s): Haggard

Conjecture   Every 2-connected graph may be embedded in a surface so that the boundary of each face is a cycle.

Keywords: cover; cycle

Cycle double cover conjecture ★★★★

Author(s): Seymour; Szekeres

Conjecture   For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two.

Keywords: cover; cycle

Syndicate content