Color Trades on Graphs

Abstract

Edge-colorings of graphs have a rich history and are widely studied. Trade spectra of graphs are relatively new and ripe for study. The color-trade-spectrum of a graph G is defined to be the set of all t for which there exist two proper edge-colorings of G using t colors such that each vertex of G is incident to the same set of colors under each edge-coloring while each edge receives a different color under each edge-coloring. We show some general results and present various constructions which are used to determine the color-trade-spectrum of several families of graphs.