×

zbMATH — the first resource for mathematics

Two classes of perfect graphs. (English) Zbl 0661.05055
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).

MSC:
05C17 Perfect graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berge, C, ()
[2] ()
[3] Bland, R.G; Huang, H.-C; Trotter, L.E, Graphical properties related to minimal imperfection, Discrete math., 27, 11-22, (1979) · Zbl 0421.05028
[4] Bondy, A; Murty, U.S.R, ()
[5] Chvátal, V, Star-cutsets and perfect graphs, J. combin. theory ser. B, 39, 189-199, (1985) · Zbl 0674.05058
[6] Chvátal, V; Sbihi, N, Bull-free graphs are perfect, Graphs and combin., 3, 127-139, (1987) · Zbl 0633.05056
[7] Gallai, T, Transitiv orientierbare graphen, Acta math. acad. sci. hungar., 18, 25-66, (1967) · Zbl 0153.26002
[8] Golumbic, M.C, ()
[9] Hsu, W.-L, How to color claw-free perfect graphs, (), 189-197 · Zbl 0479.68067
[10] Hsu, W.-L, The perfect graph conjecture on special graphs—A survey, (), 103-113
[11] Lovász, L, Normal hypergraphs and the perfect graph conjecture, Discrete math., 2, 253-267, (1972) · Zbl 0239.05111
[12] Meyniel, H, A new property of critical imperfect graphs and some consequences, European J. combin., 8, 313-316, (1987) · Zbl 0647.05053
[13] Olariu, S, Paw-free graphs, Inform. process. lett., 28, 53-54, (1988) · Zbl 0654.05063
[14] Parthasarathy, K.R; Ravindra, G, The strong perfect graph conjecture is true for K1,3-free graphs, J. combin. theory ser. B, 21, 212-223, (1976) · Zbl 0297.05109
[15] Parthasarathy, K.R; Ravindra, G, The validity of the strong perfect graph conjecture for (K_{4} − e)-free graphs, J. combin. theory ser. B, 26, 98-100, (1979) · Zbl 0416.05062
[16] Sun, L, (), Technical Report DCS-TR-228
[17] Tucker, A, Critical perfect graphs and perfect 3-chromatic graphs, J. combin. theory ser. B, 23, 143-149, (1977) · Zbl 0376.05047
[18] Tucker, A, Coloring perfect (K_{4} − e)-free graphs, J. combin. theory ser. B, 42, 313-318, (1987) · Zbl 0585.05007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.