Two classes of perfect graphs (Q1112847): Difference between revisions

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).