In graph theory, a cograph, or P4-free graph, is a graph that fulfills the following equivalent properties:

• Can be constructed from isolated vertices by complement, joint union and disjoint union.
• Can be decomposed by isolated vertex elimination and complement.
• It contains no induced path of length at least 4.
• The maximum distance between two vertices in the same connected component is at most 2.
• Has at least one pair of false or true twins (that have the same opened or closed neighbourhood).

Properties

• Polynomial recognition time:

  Since it has a characterization by a finite number of forbidden subgraphs.