The structure of apple-free graphs


M. Chudnovsky, C. Dibek, and S. Spirkl, “The structure of apple-free graphs,” Working Papers.


An apple Ak is a graph obtained from a chordless cycle Ck of length k ≥ 4 by adding a vertex that has exactly one neighbor on the cycle. A graph is apple-free if it contains no Ak, k ≥ 4, as an induced subgraph. Since every apple contains an induced claw, a chordless cycle of length at least four, and an induced path on four vertices, the class of apple-free graphs generalizes that of claw-free graphs, chordal graphs, and cographs. In this work, we provide an explicit description of the structure of all apple-free graphs.

Last updated on 12/14/2020