Paper Info
Title
On the chromatic spectrum of acyclic decompositions of graphs
Abstract
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
Year
DOI
Venue
2007
10.1002/jgt.v56:2
Journal of Graph Theory
Keywords
Field
DocType
tree,spectrum,intersection graph
Discrete mathematics,Edge coloring,Combinatorics,Bound graph,Graph power,Graph factorization,Friendship graph,Butterfly graph,Windmill graph,Mathematics,Complement graph
Journal
Volume
Issue
ISSN
56
2
0364-9024
Citations 
PageRank 
References 
2
0.65
6
Authors
2
Name
Order
Citations
PageRank
Robert E. Jamison139584.11
Eric Mendelsohn26016.58