Berge, Claude

Linial-Berge path partition duality ★★★

Author(s): Berge; Linial

\begin{conjecture} The minimum $k$-norm of a path partition on a directed graph $D$ is no more than the maximal size of an induced $k$-colorable subgraph. \end{conjecture}

Keywords: coloring; directed path; partition

The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

\begin{conjecture} If $G$ is a \Def[bridgeless]{bridge (graph theory)} \Def[cubic]{cubic graph} graph, then there exist 6 \Def[perfect matchings]{matching} $M_1,\ldots,M_6$ of $G$ with the property that every edge of $G$ is contained in exactly two of $M_1,\ldots,M_6$.


Keywords: cubic; perfect matching

Syndicate content