Rosenfeld, Moshe


Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

\begin{conjecture} Every prism over a $3$-connected cubic planar graph can be decomposed into two Hamilton cycles. \end{conjecture}

Keywords:

Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

\begin{conjecture} If $G$ is a $3$-connected planar graph, then $G\square K_2$ has a Hamilton cycle. \end{conjecture}

Keywords:

A gold-grabbing game ★★

Author(s): Rosenfeld

\textbf{ Setup} Fix a tree $T$ and for every vertex $v \in V(T)$ a non-negative integer $g(v)$ which we think of as the amount of \emph{gold} at $v$.

\textbf{2-Player game} Players alternate turns. On each turn, a player chooses a leaf vertex $v$ of the tree, takes the gold at this vertex, and then deletes $v$. The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.

\begin{problem} Find optimal strategies for the players. \end{problem}

Keywords: game; tree

Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The \emph{Odd Distance Graph}, denoted ${\mathcal O}$, is the graph with vertex set ${\mathbb R}^2$ and two points adjacent if the distance between them is an odd integer.

\begin{question} Is $\chi({\mathcal O}) = \infty$? \end{question}

Keywords: coloring; geometric graph; odd distance

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

Syndicate content