Clique Graph Recognition Is NP-Complete
DOI10.1007/11917496_24zbMATH Open1167.68403OpenAlexW1544712886MaRDI QIDQ3522963FDOQ3522963
Authors: L. Alcón, M. Gutierrez, Luerbio Faria, Celina M. H. de Figueiredo 
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
Recommendations
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)
Cited In (19)
- Split clique graph complexity
- On the iterated biclique operator
- On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
- On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
- On split clique graphs
- Title not available (Why is that?)
- On cliques of Helly Circular-arc Graphs
- Distinguishing graphs via cycles
- The number of convergent graphs under the biclique operator with no twin vertices is finite
- Edge contraction and edge removal on iterated clique graphs
- Random Graphs, Retractions and Clique Graphs
- Recognizing clique graphs of directed and rooted path graphs
- The complexity of clique graph recognition
- Almost every graph is divergent under the biclique operator
- Split clique graph complexity
- The clique operator on circular-arc graphs
- Recognizing tough graphs is NP-hard
- Clique-critical graphs: maximum size and recognition
- Biclique graphs of split graphs
This page was built for publication: Clique Graph Recognition Is NP-Complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3522963)
