On the chromatic index of path decompositions Original Research Article

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 χ′=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 mininum {χ′(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.