𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Polyhedral characterizations and perfection of line graphs

✍ Scribed by Dasong Cao; George L. Nemhauser

Book ID
104294830
Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
929 KB
Volume
81
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We give a polyhedral characterization of line graphs that. in some sense, gives a converse to Edmonds' matching theorem. We also study perfect, t-perfect and h-perfect line graphs and give polyhedral and structural characterizations.

We identify a class of h-perfect graphs that are neither perfect nor t-perfect.

πŸ“œ SIMILAR VOLUMES

Perfect k-line graphs and k-total graphs
Perfect k-line graphs and k-total graphs
✍ Van Bang LΓͺ πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 443 KB πŸ‘ 1 views

## Abstract The concept of the line graph can be generalized as follows. The __k__‐line graph __L__~__k__~(__G__) of a graph __G__ is defined as a graph whose vertices are the complete subgraphs on __k__ vertices in __G.__ Two distinct such complete subgraphs are adjacent in __L__~__k__~(__G__) if

On-line coloring of perfect graphs
On-line coloring of perfect graphs
✍ H. A. Kierstead; K. Kolossa πŸ“‚ Article πŸ“… 1996 πŸ› Springer-Verlag 🌐 English βš– 655 KB