×

Graphs without five-vertex path and four-vertex cycle. (English) Zbl 1433.05265

Summary: In this paper, we give a structure theorem for graphs containing no five-vertex path or four-vertex cycle as an induced subgraphs.

MSC:

05C75 Structural characterization of families of graphs
05C38 Paths and cycles
05C17 Perfect graphs
05C62 Graph representations (geometric and intersection representations, etc.)
PDFBibTeX XMLCite
Full Text: DOI

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.-Nat. Reihe, 10, 114-115 (1961)
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer · Zbl 1134.05001
[3] Chudnovsky, M., The structure of bull-free graphs I-three-edge-paths with centers and anticenters, J. Combin. Theory Ser. B, 102, 233-251 (2012) · Zbl 1237.05137
[4] Chudnovsky, M., The structure of bull-free graphs II and III - a summary, J. Combin. Theory Ser. B, 102, 252-282 (2012) · Zbl 1237.05138
[5] Chudnovsky, M.; Esperet, L.; Lemoine, L.; Maceli, P.; Maffray, F.; Penev, I., Graphs with no induced ve-vertex path or antipath, J. Graph Theory, 84, 221-232 (2017) · Zbl 1359.05083
[6] Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. Math., 164, 51-229 (2006) · Zbl 1112.05042
[7] Chudnovsky, M.; Seymour, P., The structure of claw-free graphs, Surv. Combinator., 153-171 (2005) · Zbl 1109.05092
[8] Chudnovsky, M.; Seymour, P.; Spirkl, S.; Zhong, M., Triangle-free graphs with no six-vertex induced path, Discrete Math., 341, 2179-2196 (2018) · Zbl 1388.05098
[9] Diot, E.; Radovanović, M.; Trotignon, N.; Vušković, K., The (theta, wheel)-free graphs part I: only-prism and only-pyramid graphs, J. Combin. Theory Ser. B (2018)
[10] Földes, S.; Hammer, P. L., Split graphs, Congr. Numer. XIX, 311-315 (1977) · Zbl 0407.05071
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.