Clique Graph Recognition Is NP-Complete

DOI10.1007/11917496_24zbMath1167.68403OpenAlexW1544712886MaRDI QIDQ3522963

Liliana Alcón, Marisa Gutierrez, Celina M. Herrera de Figueiredo, Luérbio Faria

Publication date: 4 September 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11917496_24

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

Split clique graph complexity ⋮ On cliques of Helly Circular-arc Graphs ⋮ Random Graphs, Retractions and Clique Graphs ⋮ Almost every graph is divergent under the biclique operator ⋮ Distinguishing graphs via cycles ⋮ Edge contraction and edge removal on iterated clique graphs ⋮ On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs ⋮ On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs ⋮ On the Iterated Biclique Operator ⋮ The clique operator on circular-arc graphs ⋮ The complexity of clique graph recognition ⋮ Split Clique Graph Complexity ⋮ The number of convergent graphs under the biclique operator with no twin vertices is finite ⋮ Biclique graphs of split graphs

This page was built for publication: Clique Graph Recognition Is NP-Complete