Resumen
This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the {??}
{
k
}
-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly chordal graphs, clique perfect graphs, total graphs, split graphs, line graphs, and dually chordal graphs. We give equations to compute the {??}
{
k
}
-clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the {??}
{
k
}
-clique transversal problem is polynomial-time solvable for graphs whose clique transversal numbers equal their clique independence numbers. We also show the relationship between the signed and generalization clique problems and present NP-completeness results for the considered problems on k-trees with unbounded k, planar graphs, doubly chordal graphs, total graphs, split graphs, line graphs, and dually chordal graphs.