Contraction of an even pair

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

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.