Graphs with No Induced Five‐Vertex Path or Antipath. Issue 3 (12th February 2016)

• Record Type: Journal Article
• Authors: Chudnovsky, Maria; Esperet, Louis; Lemoine, Laetitia; Maceli, Peter; Maffray, Frédéric; Penev, Irena
• Is Part Of: Journal of graph theory. Volume 84:Issue 3(2017)
• Page Start: 221
• Page End: 232
• Publication Date: 2016-02-12
• Subjects: forbidden subgraph -- P5 -- decomposition; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22022
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: We prove that a graph G contains no induced five ‐vertex path and no induced complement of a five ‐vertex path if and only if G is obtained from 5‐cycles and split graphs by repeatedly applying the following operations: substitution, split unification, and split unification in the complement, where split unification is a new class‐preserving operation introduced here.