cover

Graph Theory » Infinite Graphs

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

Posted by mdevos
updated October 23rd, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

Decomposing eulerian graphs ★★★

Author(s):

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

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

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

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

(m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

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

Keywords: cover; cycle

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

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

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

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

Posted by mdevos
updated February 7th, 2012