On split clique graphs
A complete set of a graph G is a subset of VG whose elements are pairwise adjacent. A clique is a maximal complete set. The clique graph of G, denoted by K(G), is the intersection graph of the family of cliques of G. The clique graph recognition problem asks whether a given graph is a clique graph....
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2010
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/162604 |
| Aporte de: |
| Sumario: | A complete set of a graph G is a subset of VG whose elements are pairwise adjacent. A clique is a maximal complete set. The clique graph of G, denoted by K(G), is the intersection graph of the family of cliques of G. The clique graph recognition problem asks whether a given graph is a clique graph. This problem was classified recently as NP-complete after being open for 30 years. The complexity of this decision problem is open for very structured and well studied classes of graphs such as planar graphs and chordal graphs. We propose the study of split clique graphs. |
|---|