# Contraction of an even pair

Перейти к:навигация, поиск

Contraction of an even pairстягивание четной пары.

The contraction of an even pair $\,(u,v)$ is an operation that consists in replacing the two vertices $\,u, v$ by a unique vertex $\,t$ whose neighborhood is $\,N_{G}(u) \cup N_{G}(v) - \{u,v\}$: the resulting graph is denoted by $\,G_{uv}$. 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 $\,G$ to a smaller, simpler graph with the same parameters $\,\chi$ and $\,\omega$. In the case where the final graph is a clique, $\,G$ is called even contractile; whenever this reduction can be performed not only for the graph $\,G$ itself, but also for every one of its induced subgraphs, $\,G$ is called perfectly contractile.

## Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.