𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Using stable sets to bound the chromatic number

✍ Scribed by D. de Werra; P. Hansen

Book ID
104136970
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
89 KB
Volume
87
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

A generalization of the Roy-Gallai theorem is presented: it is based on the existence in any oriented graph of a stable set S such that for any node w not in S there is an elementary path from some node of S to w. The bound obtained improves earlier results by Berge and by Li.

πŸ“œ SIMILAR VOLUMES

Playing a Game to Bound the Chromatic Nu
Playing a Game to Bound the Chromatic Number
✍ Panagiota N. Panagopoulou, Paul G. Spirakis πŸ“‚ Article πŸ“… 2012 πŸ› Mathematical Association of America 🌐 English βš– 227 KB
A Bound on the Total Chromatic Number
A Bound on the Total Chromatic Number
✍ Michael Molloy; Bruce Reed πŸ“‚ Article πŸ“… 1998 πŸ› Springer-Verlag 🌐 English βš– 481 KB
Bounds for the -chromatic number of
Bounds for the -chromatic number of
✍ Balakrishnan, R.; Francis Raj, S. πŸ“‚ Article πŸ“… 2013 πŸ› Elsevier Science 🌐 English βš– 348 KB
A bound on the chromatic number using th
A bound on the chromatic number using the longest odd cycle length
✍ Sreyash Kenkre; Sundar Vishwanathan πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 120 KB πŸ‘ 1 views

## Abstract Let __G__ be a non‐bipartite graph with β„“ as the length of the longest odd cycle. ErdΓΆs and Hajnal proved that Ο‡(__G__) ≀ β„“ + 1. We show that the only graphs for which this is tight are those that contain __K__~β„“~ + 1 and further, if __G__ does not contain __K__~β„“~ then Ο‡(__G__) ≀ β„“ βˆ’1.