|
|
|
|
|
CographIn graph theory, a cograph, complement-reducible graph , 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.
|
 |
| |
|
|