Cycle hamiltonien sur les graphiques sans petits cycles

En répondant à cette question sur cstheory , j'ai (officieusement) prouvé à la volée le théorème suivant:

Théorème : Pour tout fixe, le probem du cycle hamiltonien reste NP-complet même s'il est limité à des graphes bipartites planaires non orientés de degré 3 maximum qui ne contiennent pas de cycles de longueur ≤ l .$l \geq 3$$\leq l$

Il semble très peu probable qu'il ne soit pas déjà apparu quelque part.
Mais cela permet de régler de nombreux problèmes de cycle / chemin hamiltonien sur graphclasses.org qui sont marqués comme "inconnus de l'ISGCI" (voir par exemple celui-ci ); en effet un corollaire direct est que le cycle hamiltonien et des problèmes avec la route sont encore NP-complet si limitée à graphiques, où chacun des H i contient au moins un cycle.$(H_1,...,H_k)\text{-free}$$H_i$

Pouvez-vous me donner une référence du papier / livre où il est apparu?

(alors je contacterai les gens sur graphclasses.org)

Le résultat est indiqué dans l'article Two New Classes of Hamiltonian Graphs par Arkin, Mitchell et Polinshchuk.

Ce manuscrit inédit de Hougardy, Emden-Weinert et Kreuter en 1997 a fourni une preuve simple pour le résultat suivant qui est beaucoup plus fort que le résultat indiqué dans la réponse de Kristoffer Arnsfelt Hansen:

$0\le r <1/2$$n$$\ge n^r$

Le manuscrit contient également des résultats similaires pour d'autres problèmes tels que l'ensemble dominant, la coupe maximale, VFS, etc.