Two classes of perfect graphs (Q1112847): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:14, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two classes of perfect graphs |
scientific article |
Statements
Two classes of perfect graphs (English)
0 references
1991
0 references
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).
0 references
strong perfect graph conjecture
0 references
Gallai-perfect graphs
0 references
dart
0 references
Berge graph
0 references
dart-free Berge graphs
0 references
claw-free Berge graphs
0 references
diamond-free Berge graphs
0 references
line-graphs of bipartite graphs
0 references
bipartite graphs
0 references
dart-free perfect graphs
0 references
clique number
0 references