zbMATH — the first resource for mathematics

On clique-transversals and clique-independent sets. (English) Zbl 1013.90107
Summary: A clique-transversal of a graph \(G\) is a subset of vertices intersecting all the cliques of \(G\). A clique-independent set is a subset of pairwise disjoint cliques of \(G\). Denote by \(t_C(G)\) and \(a_C(G)\) the cardinalities of the minimum clique-transversal and maximum clique-independent set of \(G\), respectively. Say that \(G\) is clique-perfect when \(t_C(H)=a_C(H)\), for every induced subgraph \(H\) of \(G\). In this paper, we prove that every graph not containing a 4-wheel nor a 3-fan as induced subgraphs and such that every odd cycle of length greater than 3 has a short chord is clique-perfect. The proof leads to polynomial time algorithms for finding the parameters \(t_C(G)\) and \(a_C(G)\), for graphs belonging to this class. In addition, we prove that to decide whether or not a given subset of vertices of a graph is a clique-transversal is co-NP-complete. The complexity of this problem has been mentioned as unknown in the literature. Finally, we describe a family of highly clique-imperfect graphs, that is, a family of graphs \(G\) whose difference \(t_C(G)-a_C(G)\) is arbitrarily large.
Reviewer: Reviewer (Berlin)

90C27 Combinatorial optimization
90C10 Integer programming
Full Text: DOI