Article ID: | iaor20023402 |
Country: | Netherlands |
Volume: | 137 |
Issue: | 2 |
Start Page Number: | 326 |
End Page Number: | 335 |
Publication Date: | Mar 2002 |
Journal: | European Journal of Operational Research |
Authors: | Zemirline A. |
This paper introduces a structural property of minimal imperfect graphs, no minimal imperfect graph has a quasi-star-cutset, before describing some consequences. First, a large class of perfect graphs is obtained from the class of all bipartite graphs and their line-graphs; this class contains several well-known classes of perfect graphs. The second consequence deals with a composition operation of graphs which preserves perfection and which encompasses the most part of the compositions known to preserve perfection.