Graphs with No Induced Five‐Vertex Path or Antipath |
| |
| Authors: | Maria Chudnovsky Louis Esperet Laetitia Lemoine Peter Maceli Frédéric Maffray Irena Penev |
| |
| Affiliation: | 1. PRINCETON UNIVERSITY, PRINCETON, NEW JERSEY;2. CNRS, LABORATOIRE G‐SCOP, UNIVERSITY OF GRENOBLE, FRANCE;3. LABORATOIRE G‐SCOP, UNIVERSITY OF GRENOBLE, FRANCE;4. WESLEYAN UNIVERSITY, MIDDLETOWN, CONNECTICUT;5. DEPARTMENT OF APPLIED MATHEMATICS AND COMPUTER SCIENCE, TECHNICAL UNIVERSITY OF DENMARK, LYNGBY, DENMARK |
| |
| Abstract: | ![]()
We prove that a graph G contains no induced  ‐vertex path and no induced complement of a  ‐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. |
| |
| Keywords: | forbidden subgraph P5 decomposition |
|
|
‐vertex path and no induced complement of a 
‐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.