G-2001-45
Panchromatic Chains and Paths
and BibTeX reference
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.
Published November 2001 , 14 pages
Research Axes
Research applications
Document
G0145.ps (300 KB)