Juan Montoya - Mathematics, Sciences Universidad Nacional de Colombia Bogota
Laura Cadavid - Mathematics, Sciences, Universidad Nacional de Colombia, Bogota, Colombia

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.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.

fullerene, Clar Number, Benzonoids, Integer programming