On the chromatic index of path decompositions

If G = (V', E) is a graph and H = (V, H) is a graph whose edges can be decomposed into isomorphic copies of G, then we define a k-block colouring of a G-decomposition of H to be an assignment of k colours to the copies of G so that no two copies of G having a vertex in common have the same colour. A G-decomposition of H has chromatic index chi' = k if it is k block colourable and not k - 1 block colourable. We use the techniques of G-resolvable designs and G-frames to solve the Minimal Chromatic Index Problem: Given H determine minimum {chi'(D)\D is a G-decomposition of H} and exhibit a D that achieves this minimum, for the cases where H the complete graph on n vertices and G is the path of length 2 or 3. (C) 2004 Published by Elsevier B.V.