# Clique-transversal

(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

A clique-transversal of a graph $\displaystyle{ 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 $\displaystyle{ G }$, denoted by $\displaystyle{ \tau_{c}(G) }$ and $\displaystyle{ \alpha_{c}(G) }$, are the sizes of a minimum clique-transversal and a maximum clique-independent set of $\displaystyle{ G }$, respectively.

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