Group for Research in Decision Analysis

G-2001-45

Panchromatic Chains and Paths

and

A generalization of the Roy-Gallai theorem on the chromatic number of a graph is derived which is also an extension of several other results of Berge and of Li. A simple inductive proof is given which provides a direct way of deriving the theorem of Li. We also show that any k-chromatic graph contains at least k! chains meeting every color exactly once.

, 14 pages