A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

\begin{conjecture} Let $H$ be a simple $d$-\Def[uniform]{hypergraph} hypergraph, and assume that every set of $d-1$ points is contained in at most $r$ edges. Then there exists an $r+d-1$-edge-coloring so that any two edges which share $d-1$ vertices have distinct colors. \end{conjecture}

Keywords: edge-coloring; hypergraph; Vizing

Ryser's conjecture ★★★

Author(s): Ryser

\begin{conjecture} Let $H$ be an $r$-\Def[uniform]{hypergraph} $r$-partite hypergraph. If $\nu$ is the maximum number of pairwise disjoint edges in $H$, and $\tau$ is the size of the smallest set of vertices which meets every edge, then $\tau \le (r-1) \nu$. \end{conjecture}

Keywords: hypergraph; matching; packing

Syndicate content