𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On-line coloring of perfect graphs

✍ Scribed by H. A. Kierstead; K. Kolossa

Publisher
Springer-Verlag
Year
1996
Tongue
English
Weight
655 KB
Volume
16
Category
Article
ISSN
0209-9683

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

On line perfect graphs
On line perfect graphs
✍ D. de Werra πŸ“‚ Article πŸ“… 1978 πŸ› Springer-Verlag 🌐 English βš– 150 KB
Coloring quasi-line graphs
Coloring quasi-line graphs
✍ Maria Chudnovsky; Alexandra Ovetsky πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 127 KB

## Abstract A graph __G__ is a quasi‐line graph if for every vertex __v__, the set of neighbors of __v__ can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if __G__ is a line graph, then