Variations on the Roy-Gallai theorem

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 some classical results valid...

Full description

Saved in:
Bibliographic Details
Published in:4OR 2005-09, Vol.3 (3), p.243-251
Main Authors: Werra, Dominique de, Hansen, Pierre
Format: Article
Language:English
Subjects:
Operations research
Studies
Theorems
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 some classical results valid for optimal colorings cannot be transposed to suboptimal colorings. We finally investigate some elementary properties which are also valid in suboptimal colorings.
ISSN:1619-4500
1614-2411
DOI:10.1007/s10288-004-0043-9