On the chromatic spectrum of acyclic decompositions of graphs

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. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 83–104, 2007