|
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.
|
