zbMATH — the first resource for mathematics

Paw-free graphs. (English) Zbl 0654.05063
The graph with vertices $$a, b, c, d$$ and edges $$ab, bc, bd, cd$$ will be referred to as the paw. A graph $$G$$ is called paw-free if it contains no induced subgraph isomorphic to the paw. We characterize paw-free graphs and give polynomial-time algorithms for recognizing them as well as algorithms for finding the largest clique and the largest stable set in a paw-free graph.
Reviewer: Stephan Olariu

MSC:
 05C17 Perfect graphs 05C85 Graph algorithms (graph-theoretic aspects) 05C35 Extremal problems in graph theory 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science
Full Text:
References:
 [1] Berge, C., Färbung von graphen deren sämtliche bzw. deren ungerade kreise starr sind, Wiss. Z. martin-luther univ. halle-Wittenberg math.-natur reihe, 114-115, (1961) [2] Berge, C.; Chvátal, V., Topics on perfect graphs, () · Zbl 0546.00006 [3] Berge, C.; Duchet, P., Strongly perfect graphs, (), 57-61 · Zbl 0558.05037 [4] Burlet, M.; Fonlupt, J., Polynomial algorithm to recognize a meyniel graph, (), 225-252 · Zbl 0558.05055 [5] Chvätal, V., Perfectly ordered graphs, (), 63-65 · Zbl 0559.05055 [6] Chvätal, V.; Sbihi, N., Recognizing claw-free perfect graphs, (1985), School of Computer Science, McGill Univ Montréal, Tech. Rept., SOCS-85.6 · Zbl 0669.05054 [7] Corneil, D.G.; Perl, Y.; Stewart, L., A linear recognition algorithm for cographs, SIAM J. comput., 14, 926-934, (1985) · Zbl 0575.68065 [8] Duchet, P.; Olariu, S., Graphes parfaitement ordonnables généralisés, (), 27-30 · Zbl 0743.05043 [9] Hsu, W.L., On the existence of induced odd cycles in planar graphs, (1984), Northwestern Univ Evanston, IL, Res. Rept. [10] H. Meyniel, A new property of critical imperfect graphs and some consequences, Europ. J. Combinatorics, to appear. · Zbl 0647.05053
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.