The complexity of clique graph recognition
From MaRDI portal
Publication:1019185
DOI10.1016/j.tcs.2009.01.018zbMath1168.68015OpenAlexW2086520272MaRDI QIDQ1019185
Celina M. Herrera de Figueiredo, Marisa Gutierrez, Liliana Alcón, Luérbio Faria
Publication date: 28 May 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://sedici.unlp.edu.ar/handle/10915/82662
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 (16)
On the iterated edge-biclique operator ⋮ On second iterated clique graphs that are also third iterated clique graphs ⋮ The Images of the Clique Operator and Its Square are Different ⋮ Split clique graph complexity ⋮ On the edge‐biclique graph and the iterated edge‐biclique operator ⋮ Intersection graph of maximal stars ⋮ Discrete Morse theory and the homotopy type of clique graphs ⋮ Edge contraction and edge removal on iterated clique graphs ⋮ Unnamed Item ⋮ Characterization of classical graph classes by weighted clique graphs ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ On edge-sets of bicliques in graphs ⋮ Split Clique Graph Complexity ⋮ On the clique behavior of circulants with three small jumps ⋮ The difference between clique graphs and iterated clique graphs ⋮ Vertex removal in biclique graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Convergence of iterated clique graphs
- Recognizing clique graphs of directed and rooted path graphs
- On clique divergent graphs with linear growth
- On clique-complete graphs
- The clique operator on cographs and serial graphs
- Dismantlings and iterated clique graphs
- Cliques and extended triangles. A necessary condition for planar clique graphs
- Distances and diameters on iterated clique graphs
- On clique-critical graphs
- On clique convergent graphs
- On hereditary clique-Helly self-clique graphs
- Clique-critical graphs: maximum size and recognition
- A characterization of clique graphs
- Über iterierte Clique-Graphen
- Graph relations, clique divergence and surface triangulations
- On cliques of Helly Circular-arc Graphs
- Clique Graph Recognition Is NP-Complete
- Dually Chordal Graphs
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- A common generalization of line graphs and clique graphs
- 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
- Intersection graphs and the clique operator
This page was built for publication: The complexity of clique graph recognition
