Computing the clar number of nanotubes and other fullerenes

Abstract

We exhibit a polynomial time algorithm that computes the Clar number of any nanotube. This algorithm can be easily extended to one that computes the Clar number of fullerene whose pentagon-clusters are all of even size.<br /> <br /> It is known that computing the Clar number of planar graphs is NP-hard. It is not known if computing the Clar number of fullerenes is a tractable problem. We show that the latter problem can be suitably approximated in polynomial time, and we also discuss the existence of fpt-algorithms for this important problem of Cheminformatics.