Гамильтонов цикл на графах без малых циклов

Отвечая на этот вопрос о теории , я (неформально) на лету доказал следующую теорему:

Теорема : Для любого фиксированного пробел гамильтонова цикла остается NP-полным, даже если он ограничен планарными двудольными неориентированными графами максимальной степени 3, которые не содержат циклов длины ≤ l .$l \geq 3$$\leq l$

Кажется очень маловероятным, что он еще не появился где-то.
Но это позволяет решить многие гамильтоновы проблемы цикла / пути на graphclasses.org, помеченные как «Неизвестно для ISGCI» (см., Например, этот ); на самом деле является прямым следствием является то , что гамильтонов цикл и пути проблемы все еще NP-полной , если ограничено графики, где каждый из Н я содержит , по меньшей мере , один цикл.$(H_1,...,H_k)\text{-free}$$H_i$

Можете ли вы дать мне ссылку на бумагу / книгу, где она появилась?

(тогда я свяжусь с людьми на graphclasses.org)

Результат изложен в статье « Два новых класса гамильтоновых графов » Аркина, Митчелла и Полинщука.

Эта неопубликованная рукопись Хугарди, Эмдена-Вейнерта и Кройтера в 1997 году дала простое доказательство следующего результата, который намного сильнее, чем результат, указанный в ответе Кристоффера Арнсфельта Хансена:

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

Рукопись также содержит аналогичные результаты для других задач, таких как Доминирующий набор, Максимальное сокращение, VFS и т. Д.