𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some perfect coloring properties of graphs

✍ Scribed by Claude A Christen; Stanley M Selkow

Publisher
Elsevier Science
Year
1979
Tongue
English
Weight
630 KB
Volume
27
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Coloring precolored perfect graphs
Coloring precolored perfect graphs
✍ KratochvοΏ½l, Jan; Seb?, AndrοΏ½s πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 115 KB πŸ‘ 2 views

We consider the question of the computational complexity of coloring perfect graphs with some precolored vertices. It is well known that a perfect graph can be colored optimally in polynomial time. Our results give a sharp border between the polynomial and NP-complete instances, when precolored vert

Uniquely colorable perfect graphs
Uniquely colorable perfect graphs
✍ Alan Tucker πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 883 KB
Perfect coloring and linearly Ο‡-bound P6
Perfect coloring and linearly Ο‡-bound P6-free graphs
✍ S. A. Choudum; T. Karthick; M. A. Shalu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 169 KB

## Abstract We derive decomposition theorems for __P__~6~, __K__~1~ + __P__~4~‐free graphs, __P__~5~, __K__~1~ + __P__~4~‐free graphs and __P__~5~, __K__~1~ + __C__~4~‐free graphs, and deduce linear χ‐binding functions for these classes of graphs (here, __P__~__n__~ (__C__~__n__~) denotes the path