G-2001-45
Panchromatic Chains and Paths
et référence BibTeX
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.
Paru en novembre 2001 , 14 pages
Axes de recherche
Applications de recherche
Document
G0145.ps (270 Ko)