Split clique graph complexity

DOI10.1016/j.tcs.2013.07.020zbMath1416.68127MaRDI 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-completeness; clique graph; split graphs; Helly property

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

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