Split clique graph complexity

DOI10.1016/j.tcs.2013.07.020zbMath1416.68127OpenAlexW2040819829MaRDI QIDQ393107

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

Publication date: 16 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.07.020

zbMATH Keywords

NP-completenessclique graphsplit graphsHelly property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The clique operator on circular-arc graphs
• The complexity of clique graph recognition
• Recognizing clique graphs of directed and rooted path graphs
• On clique-complete graphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• The clique operator on cographs and serial graphs
• Cliques and extended triangles. A necessary condition for planar clique graphs
• Complexity aspects of the Helly property: graphs and hypergraphs
• A characterization of clique graphs
• Graph relations, clique divergence and surface triangulations
• Clique Graph Recognition Is NP-Complete
• Dually Chordal Graphs
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Clique Graphs of Chordal and Path Graphs
• Self‐clique graphs and matrix permutations
• Clique-inverse graphs ofK3-free andK4-free graphs
• A partial characterization of clique graphs