Contraction of an even pair

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

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

Литература

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