Two classes of perfect graphs
Claude Berge proposed to call a graph perfect if, for each of its induced subgraph \(F\), the chromatic number of \(F\) equals the largest number of pairwise adjacent vertices in \(F\). An odd hole is a chordless cycle whose number of vertices is odd and at least five. Berge conjectured that a graph is perfect if and only if none of its induced subgraphs is an odd hole or the complement of an odd hole. This is known as the Strong perfect graph conjecture. The only if part is trivial; the if part is still open. Chvátal suggested considering the following class of Berge graphs (that is, graphs with no induced subgraph isomorphic to an odd hole or the complement of an odd hole): First, given any graph \(G\), define a graph \(\mathrm{Gal}(G)\) by letting the vertices of \(\mathrm{Gal}(G)\) be the edges of \(G\), and making two vertices of \(\mathrm{Gal}(G)\) adjacent if and only if the corresponding two edges of \(G\) share an endpoint and their other two endpoints are nonadjacent in \(G\) (so that the two edges form a chordless path with three vertices in \(G\)). We call a graph \(G\) Gallai-perfect if, and only if, \(\mathrm{Gal}(G)\) contains no odd hole. We prove that every Gallai-perfect graph is perfect. The class of Gallai-perfect graphs includes all bipartite graphs, all complements of bipartite graphs, and all line-graphs of bipartite graphs. A dart is the graph with vertices \(a, b, c, d, e\) and edges \(ab, ac, bc, bd, cd, be\). We prove that every Berge graph with no induced subgraph isomorphic to a dart is perfect. The class of dart-free Berge graphs includes all claw-free Berge graphs (which, in turn, include all line- graphs of bipartite graphs and all complements of bipartite graphs) as well as all diamond-free Berge graphs (which, in turn, include all line- graphs of bipartite graphs as well as bipartite graphs).
- Classes of perfect graphs
- New classes of perfect graphs
- Some classes of strongly perfect graphs
- On perfectly two-edge connected graphs
- A class of strongly perfect graphs
- On some graph classes related to perfect graphs: a survey
- scientific article; zbMATH DE number 4065042
- scientific article; zbMATH DE number 1455118
- Perfect graphs
- scientific article; zbMATH DE number 3851153
- A new property of critical imperfect graphs and some consequences
- Bull-free Berge graphs are perfect
- Coloring perfect \((K_ 4\)-e)-free graphs
- Critical perfect graphs and perfect 3-chromatic graphs
- Graph theory with applications
- Graphical properties related to minimal imperfection
- How To Color Claw-Free Perfect Graphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3902680 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- Normal hypergraphs and the perfect graph conjecture
- Paw-free graphs
- Star-cutsets and perfect graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- The validity of the strong perfect-graph conjecture for (K₄-e)-free graphs
- Topics on perfect graphs
- Transitiv orientierbare Graphen
- Alternating orientation and alternating colouration of perfect graphs
- Gallai graphs and anti-Gallai graphs
- Some properties of minimal imperfect graphs
- On minimal imperfect graphs without induced P₅
- A description of claw-free perfect graphs
- Mortality of iterated Gallai graphs
- New classes of Berge perfect graphs
- Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
- On perfectly two-edge connected graphs
- Chair-free Berge graphs are perfect
- Quasi-star-cutsets and some consequences
- A transformation which preserves the clique number
- On dart-free perfectly contractile graphs
- Infinite \(\Phi\)-periodic graphs
- On the \(P_ 4\)-structure of perfect graphs. V: Overlap graphs
- Two classes of \(\beta \)-perfect graphs that do not necessarily have simplicial extremes
- Gallai and anti-Gallai graph operators
- Classes of perfect graphs
- Some conjectures on perfect graphs
- Recognizing Perfect 2-Split Graphs
- scientific article; zbMATH DE number 1445285 (Why is no real title available?)
- A survey of the studies on Gallai and anti-Gallai graphs
- On an edge partition and root graphs of some classes of line graphs
- EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS
- Skeletal graphs - a new class of perfect graphs
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- On perfect switching classes
- Revisit the coloring problem of Gallai graphs
- A class of h-perfect graphs
- The strong perfect graph theorem
- Decomposing Berge graphs containing no proper wheel, long prism or their complements
This page was built for publication: Two classes of perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1112847)