𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A characterization of normal fraternally orientable perfect graphs

✍ Scribed by H. Galeana-Sánchez

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
255 KB
Volume
169
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

While the famous Berge's Strong Perfect Graph Conjecture remains a major unsolved problem in Graph Theory, the following alternative characterization of perfect graphs was conjectured in 1982 by C. Berge and P. Duchet: A graph G is perfect if and only if any normal orientation of G is kernel-perfect. In this paper I prove the validity of a version of this conjecture for graphs which accept a normal fraternal orientation.

📜 SIMILAR VOLUMES

Normal fraternally orientable graphs sat
Normal fraternally orientable graphs satisfy the strong perfect graph conjecture
✍ H. Galeana-Sánchez 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 718 KB

The chromatic number x of a graph G is the minimum number of colors necessary to color the vertices of G such that no two adjacent vertices are colored alike. The clique number 01 of a graph G is the maximum number of vertices in a complete subgraph of G. A graph G is said to be perfect if x(H) =m(H

A characterization of domination perfect
A characterization of domination perfect graphs
✍ I. E. Zverovich; V. E. Zverovich 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB

Let u(G) and i(G) be the domination number and independent domination number of a graph G. respectively. Sumner and Moore [8] define a graph G to be domination perfect if y( H) = i( H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization o

A Characterization of b-Perfect Graphs
A Characterization of b-Perfect Graphs
✍ Chính T. Hoàng; Frédéric Maffray; Meriem Mechebbek 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 316 KB

## Abstract A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph __G__ is the largest integer __k__ such that __G__ admits a b‐coloring with __k__ colors. A graph is b