Ciclo hamiltoniano em gráficos sem pequenos ciclos

Ao responder a essa pergunta sobre a teoria , eu (informalmente) provei rapidamente o seguinte teorema:

Teorema : Para qualquer fixo ≥ 3, o probem do ciclo hamiltoniano permanece NP-completo, mesmo que restrito a gráficos bipartidos planas não direcionados de grau máximo 3 que não contenham ciclos de comprimento ≤ l .$l \geq 3$$\leq l$

Parece muito improvável que ele ainda não tenha aparecido em algum lugar.
Mas permite resolver muitos problemas de ciclo / caminho hamiltonianos no graphclasses.org marcados como "Desconhecido para ISGCI" (veja, por exemplo, este ); de facto um corolário directa é que os problemas de ciclo e de caminho hamiltonianas ainda são NP-se completa restrita a gráficos, onde cada um de a H i contém, pelo menos, um ciclo.$(H_1,...,H_k)\text{-free}$$H_i$

Você pode me dar uma referência do papel / livro onde ele apareceu?

(entrarei em contato com pessoas em graphclasses.org)

O resultado é afirmado no artigo Duas Novas Classes de Gráficos Hamiltonianos, de Arkin, Mitchell e Polinshchuk.

Este manuscrito não publicado de Hougardy, Emden-Weinert e Kreuter em 1997 forneceu uma prova simples para o seguinte resultado, que é muito mais forte do que o resultado apontado na resposta de Kristoffer Arnsfelt Hansen:

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

O manuscrito também contém resultados semelhantes para outros problemas, como Dominação, Max cut, VFS, etc.