On clique-transversals and clique-independent sets

DOI10.1023/A:1021363810398zbMath1013.90107MaRDI QIDQ1854773

Guillermo Durán, Min Chih Lin, Jayme Luiz Szwarcfiter

Publication date: 27 January 2003

Published in: Annals of Operations Research (Search for Journal in Brave)

zbMATH Keywords

linear programminginteger linear programmingclique-transversalsclique-perfect graphsclique-independent setshighly clique-imperfect graphs

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (27)

The algorithmic complexity of the minus clique-transversal problem ⋮ The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs ⋮ Clique-transversal number of graphs whose clique-graphs are trees ⋮ Clique-perfectness and balancedness of some graph classes ⋮ On some graph classes related to perfect graphs: a survey ⋮ Weighted maximum-clique transversal sets of graphs ⋮ Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs ⋮ Variations of maximum-clique transversal sets on graphs ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ The clique-transversal set problem in claw-free graphs with degree at most 4 ⋮ Algorithms for finding clique-transversals of graphs ⋮ Bounds on the clique-transversal number of regular graphs ⋮ Clique-perfectness of claw-free planar graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs ⋮ Distance-hereditary graphs are clique-perfect ⋮ Signed and minus clique-transversal functions on graphs ⋮ Algorithms for clique-independent sets on subclasses of circular-arc graphs ⋮ Signed clique-transversal functions in graphs ⋮ The \(\langle t \rangle \)-property of some classes of graphs ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ Clique-perfectness of complements of line graphs ⋮ Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs ⋮ The clique-perfectness and clique-coloring of outer-planar graphs ⋮ Approximation algorithms for clique transversals on some graph classes ⋮ Hitting all maximal independent sets of a bipartite graph

This page was built for publication: On clique-transversals and clique-independent sets