# Hamiltonian cycle on graphs without small cycles

While answering this question on cstheory, I (informally) proved on the fly the following theorem:

Theorem: For any fixed $l \geq 3$ the Hamiltonian cycle probem remains NP-complete even if restricted to planar bipartite undirected graphs of maximum degree 3 that don't contain cycles of length $\leq l$.

It seems very unlikely that it has not already appeared somewhere.
But it allows to settle many Hamiltonian cycle/path problems on graphclasses.org that are marked as "Unknown to ISGCI" (see for example this one); indeed a direct corollary is that Hamiltonian cycle and path problems are still NP-complete if restricted to $(H_1,...,H_k)\text{-free}$ graphs, where each of the $H_i$ contains at least one cycle.

Can you give me a reference of the paper/book where it appeared?

(then I'll contact people at graphclasses.org)

• At least these discussions helped for new results in graphclasses.org so please inform graphclasses about unknown to them result - The Contact link gives a form, email address is optional. – joro Jun 18 '14 at 8:02
• @joro: I already contacted them, yesterday (I also gave them my email). I'll wait a few days and see if they update the status of those problems. – Marzio De Biasi Jun 18 '14 at 8:42
• I heard they don't update the database very often and reply with "thanks" after updating the DB and they are quite responsive. – joro Jun 18 '14 at 9:04
• @joro: I think they updated the database (they are very collaborative and polite) – Marzio De Biasi Jun 23 '14 at 7:27

For any given rational number $0\le r <1/2$, the Hamiltonian cycle probem remains NP-complete even if restricted to bipartite planar $n$-vertex graphs of maximum degree 3 and girth $\ge n^r$.