Strong matchings and covers ★★★

Author(s): Aharoni

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

\begin{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. \end{conjecture}

Keywords: cover; infinite graph; matching

Decomposing eulerian graphs ★★★


\begin{conjecture} If $G$ is a 6-\Def[edge-connected]{connectivity (graph theory)} \Def[Eulerian graph]{eulerian graph} and $P$ is a 2-transition system for $G$, then $(G,P)$ has a compaible decomposition. \end{conjecture}

Keywords: cover; cycle; Eulerian

Faithful cycle covers ★★★

Author(s): Seymour

\begin{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. \end{conjecture}

Keywords: cover; cycle

(m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph has a (5,2)-cycle-cover. \end{conjecture}

Keywords: cover; cycle

The circular embedding conjecture ★★★

Author(s): Haggard

\begin{conjecture} Every 2-\Def[connected]{connectivity (graph theory)} graph may be \Def[embedded]{graph embedding} in a surface so that the boundary of each face is a cycle. \end{conjecture}

Keywords: cover; cycle

Cycle double cover conjecture ★★★★

Author(s): Seymour; Szekeres

\begin{conjecture} For every graph with no \Def[bridge]{bridge (graph theory)}, there is a list of cycles so that every edge is contained in exactly two. \end{conjecture}

Keywords: cover; cycle

Syndicate content