A complete set of a graph G is a subset of V inducing a complete subgraph. A clique is a maximal complete set. Denote by the clique family of G. The clique graph of G, denoted by K(G), is the intersection graph of . Say that G is a clique graph if there exists a graph H such that G=K(H). The clique graph recognition problem asks whether a given graph is a clique graph. A sufficient condition was given by Hamelink in 1968, and a characterization was proposed by Roberts and Spencer in 1971. We prove that the clique graph recognition problem is NP-complete.
Información general
Fecha de exposición:2006
Fecha de publicación:2006
Idioma del documento:Inglés
Evento:32nd International Workshop (WG 2006) (Bergen, Norway, June 22-24, 2006)
Institución de origen:Facultad de Ciencias Exactas
Excepto donde se diga explícitamente, este item se publica bajo la siguiente licencia Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)