(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 K3 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.


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

Revised: May 25, 2006.