A generalization of Vizing's Theorem?

Importance: Medium ✭✭
Author(s): Rosenfeld, Moshe
Subject: Graph Theory
» Coloring
» » Edge coloring
Recomm. for undergrads: no
Posted by: mdevos
on: April 11th, 2007
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.

Vizing's Theorem is equivalent to the above statement for $ d=2 $. For higher dimensions, this problem looks difficult since the main tool used in the proof of Vizing's theorem (Kempe chains) do not appear to work.


Could someone please add a reference? There should be some paper (or a conference talk?) where Rosenfeld proposed the conjecture.


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.