Retour

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.

, 14 pages

Axes de recherche

Applications de recherche

Document

G0145.ps (270 Ko)