QP-2011-07

NP-hardness of the Clar number in general plane graphs

Attila Bernáth, Erika Renáta Bérczi-Kovács



Abstract

We prove that calculating the Clar number in general plane graphs is NP-hard.


Bibtex entry:

@techreport{egresqp-11-07,
AUTHOR = {Bern{\'a}th, Attila and B{\'e}rczi-Kov{\'a}cs Ren{\'a}ta, Erika},
TITLE = {NP-hardness of the Clar number in general plane graphs},
NOTE= {{\tt egres.elte.hu}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2011},
NUMBER = {QP-2011-07}
}


Last modification: 6.4.2021. Please email your comments to Tamás Király!