| dc.creator | Alcón, Liliana Graciela | |
| dc.date | 2006 | |
| dc.date | 2019-10-11T18:28:37Z | |
| dc.identifier | http://sedici.unlp.edu.ar/handle/10915/83201 | |
| dc.identifier | issn:0166-218X | |
| dc.description | The clique graph of G, K (G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K<SUB>-1</SUB> (G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete. | |
| dc.description | Facultad de Ciencias Exactas | |
| dc.format | application/pdf | |
| dc.format | 1799-1802 | |
| dc.language | en | |
| dc.rights | http://creativecommons.org/licenses/by-nc-sa/4.0/ | |
| dc.rights | Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) | |
| dc.subject | Ciencias Exactas | |
| dc.subject | Clique graphs | |
| dc.subject | Clique-critical graphs | |
| dc.subject | NP-complete problems | |
| dc.title | Clique-critical graphs: Maximum size and recognition | |
| dc.type | Articulo | |
| dc.type | Articulo | |
