Premium
On the chromatic spectrum of acyclic decompositions of graphs
Author(s) -
Jamison Robert E.,
Mendelsohn Eric
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20248
Subject(s) - mathematics , combinatorics , partition (number theory) , bipartite graph , spectrum (functional analysis) , graph , chromatic polynomial , discrete mathematics , physics , quantum mechanics
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