Clique Graph Recognition Is NP-Complete

DOI10.1007/11917496_24MaRDI QIDQ3522963zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

Recommendations

• The complexity of clique graph recognition
• On split clique graphs
• Split clique graph complexity
• Split clique graph complexity
• scientific article; zbMATH DE number 2188421

Cited in

(21)

• The complexity of clique graph recognition
• Recognizing clique graphs of directed and rooted path graphs
• On clique-complete graphs
• Biclique graphs of split graphs
• Edge contraction and edge removal on iterated clique graphs
• Clique-critical graphs: maximum size and recognition
• Distinguishing graphs via cycles
• The number of convergent graphs under the biclique operator with no twin vertices is finite
• On split clique graphs
• Split clique graph complexity
• On cliques of Helly Circular-arc Graphs
• Random Graphs, Retractions and Clique Graphs
• Split clique graph complexity
• On the iterated biclique operator
• scientific article; zbMATH DE number 2188421 (Why is no real title available?)
• On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
• On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
• Distinguishing graphs via cycles
• Almost every graph is divergent under the biclique operator
• Recognizing tough graphs is NP-hard
• The clique operator on circular-arc 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)