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 2 c  + 1. If G is a forest, then there is a tree T whose G ‐spectrum contains both 2 and 2 c . 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