Groupe d’études et de recherche en analyse des décisions


Panchromatic Chains and Paths


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