On the Chromatic Spectrum of Acyclic Decompositions of Graphs
by
Robert E. Jamison
Clemson University, and University of Haifa
Coauthors: Eric Mendelsohn

If G is any graph, a G-decomposition of a host graph H=(V, E) is a partition of the edge set of H into subgraphs of H which are isomorphic to G. The chromatic index of a G-decomposition is the minimum number of colors required to color the parts of the decomposition so that two parts which share a node get different colors. The G-spectrum of H is the set of all chromatic indices taken on by G-decompositions of H.

If both S and T are trees, then the S-spectrum of T consists of a single value which can be computed in polynomial time. On the other hand, for any fixed tree S, not a single edge, there is a unicyclic host whose S-spectrum has two values, and if the host is allowed to be arbitrary, the S-spectrum can take on arbitrarily many values. Moreover, deciding if an integer k is in the S-spectrum of a general bipartite graph is NP-hard.

We show that if G has c > 1 components, then there is a host H whose G-spectrum contains both 3 and 2c+1. If G is a forest, then there is a tree T whose G-spectrum contains both 2 and 2c. Furthermore, we determine the complete spectra of both paths and cycles with respect to matchings.

Date received: May 1, 2008