## (r,s)-edge-choosability of graphs

Let r and s be positive integers, where r > s. A graph G is (r,s)-colorable
if for every vertex v of G there is an s-set C(v) of colors from {1,2,...,r}
such that C(v) and C(u) are disjoint whenever v and u are adjacent in G. One can
extend this definition to (r,s)-edge-colorings and also to list colorings where
all lists have cardinality r. In such a way, one also defines (r,s)-edge-choosability.

**Problem 1: **Is it
true that every cubic graph is (8,2)-edge-choosable?

**Problem 2: **Is it
true that every connected graph distinct from K_{3} of maximum degree D
is (2D+1,2)-edge-colorable?

It is possible that both problems have positive answers. I did not explore
these problems in as much detail to be sure to exclude some trivial
counterexamples. In Problem 1, (8,2) could possibly be replaced by (7,2) (for
which the Petersen graph is the most obvious candidate for a counterexample).

In Problem 2, a weaker version would ask about (3D+2,3)-edge-colorability.

These two problems have vague relationship to the fractional chromatic index.

References:

Send comments to Bojan.Mohar@uni-lj.si

##### Revised: May 25, 2006.