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.

Литература

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