# Clique-transversal

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

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.