Clique-transversal

Материал из WikiGrapp
Версия от 13:35, 3 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Clique-transversal''' --- кликовая трансверсаль. A '''clique-transversal''' of a graph <math>G</math> is a subset of vertices that meets all…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Clique-transversal --- кликовая трансверсаль.

A clique-transversal of a graph G is a subset of vertices that meets all the cliques. A clique-independent set is a collection of pairwise vertex disjoint cliques. The clique-transversal number and clique-independence number of G, denoted by \tau_{c}(G) and \alpha_{c}(G), are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively.

It is easy to see that \tau_{c}(G) \geq \alpha_{c}(G) for any graph G. A graph G is clique-perfect if \tau_{c}(H) =
\alpha_{c}(H) for every induced subgraph H of G. If this equality holds for the graph G, we say that G is clique-good.