Home » Author index

Rosenfeld, Moshe


Graph Theory » Basic G.T. » Cycles

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

Author(s): Alspach; Rosenfeld

Conjecture   Every prism over a $ 3 $-connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

Posted by fhavet
updated March 12th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

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

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

Conjecture   If $ G $ is a $ 3 $-connected planar graph, then $ G\square K_2 $ has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment
Graph Theory » Graph Algorithms

A gold-grabbing game ★★

Author(s): Rosenfeld

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 gold at $ v $.

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.

Problem   Find optimal strategies for the players.

Keywords: game; tree

Posted by mdevos
updated October 4th, 2009
1 comment
Graph Theory » Coloring » Vertex coloring

Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The 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.

Question   Is $ \chi({\mathcal O}) = \infty $?

Keywords: coloring; geometric graph; odd distance

Posted by mdevos
updated March 19th, 2012
8 comments
Graph Theory » Coloring » Edge coloring

A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

Conjecture   Let $ H $ be a simple $ d $-uniform 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.

Keywords: edge-coloring; hypergraph; Vizing

Posted by mdevos
updated June 23rd, 2009
1 comment
Syndicate content