𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A generalization of simplicial elimination orderings

✍ Scribed by Maffray, Fr�d�ric; Porto, Oscar; Preissmann, Myriam

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
371 KB
Volume
23
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the class of graphs where every induced subgraph possesses a vertex whose neighborhood has no P4 and no 2K2. We prove that Berge's Strong Perfect Graph Conjecture holds for such graphs. The class generalizes several well-known families of perfect graphs, such as triangulated graphs and bipartite graphs. Testing membership in this class and computing the maximum clique size for a graph in this class is not hard, but finding an optimal coloring is NP-hard. We give a polynomial-time algorithm for optimally coloring the vertices of such a graph when it is perfect. 0 1996

📜 SIMILAR VOLUMES

Perfect elimination orderings of chordal
Perfect elimination orderings of chordal powers of graphs
✍ Andreas Brandstädt; Victor D. Chepoi; Feodor F. Dragan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 378 KB

Let G = (V,E) be a finite undirected connected graph. We show that there is a common perfect elimination ordering of all powers of G which represent chordal graphs. Consequently, if G and all of its powers are chordal then all these graphs admit a common perfect elimination ordering. Such an orderin