Chromatically Supremal Decompositions of Graphs |
| |
Authors: | Robert E. Jamison Eric Mendelsohn |
| |
Affiliation: | 1. Discrete Mathematics, Clemson University, Clemson, SC, 29634-0975, USA 2. University of Haifa, Haifa, Israel 3. Department of Mathematics, University of Toronto, Toronto, ON, M5S 3G3, Canada
|
| |
Abstract: | If G is a graph, a G-decomposition of a host graph H is a partition of the edges of H into subgraphs of H which are isomorphic to G. The chromatic index of a G-decomposition of H is the minimum number of colors required to color the parts of the decomposition so that parts which share a common node get different colors. We establish an upper bound on the chromatic index and characterize those decompositions which achieve it. The structurally most interesting of the decompositions with maximal chromatic index are associated with (v, k, 1)-designs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|