Contraction of an even pair
Contraction of an even pair — стягивание четной пары.
The contraction of an even pair is an operation that consists in replacing the two vertices by a unique vertex whose neighborhood is : the resulting graph is denoted by . Contracting an even pair preserves the chromatic number and clique number. Thus, successive contraction of even pairs could possibly be used to reduce a given graph to a smaller, simpler graph with the same parameters and . In the case where the final graph is a clique, is called even contractile; whenever this reduction can be performed not only for the graph itself, but also for every one of its induced subgraphs, is called perfectly contractile.
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.