Hamilton-Zyklus auf Graphen ohne kleine Zyklen

Bei der Beantwortung dieser Frage auf cstheory habe ich (informell) das folgende Theorem im Fluge bewiesen:

Theorem : Für jede feste der Hamilton - Operator Zyklus probem bleibt NP-complete auch eingeschränkt , wenn bipartite ungerichtete Graphen der maximalen Grad planar 3, die keine Zyklen der Länge enthalten ≤ l .$l \geq 3$$\leq l$

Es ist sehr unwahrscheinlich, dass es noch nicht irgendwo aufgetaucht ist.
Aber es erlaubt, viele Hamiltonsche Rad- / Wegprobleme auf graphclasses.org zu lösen, die als "ISGCI unbekannt" markiert sind (siehe zum Beispiel dieses ); in der Tat eine direkte Folge ist , dass Hamilton - Zyklus und Pfadprobleme , wenn noch NP-vollständig sind beschränkt auf Graphen, wobei jeder der H i mindestens einen Zyklus enthält.$(H_1,...,H_k)\text{-free}$$H_i$

Können Sie mir eine Referenz des Papiers / Buches geben, in dem es erschienen ist?

(dann melde ich mich bei graphclasses.org)

Das Ergebnis ist in der Arbeit Two New Classes of Hamiltonian Graphs von Arkin, Mitchell und Polinshchuk angegeben.

Dieses unveröffentlichte Manuskript von Hougardy, Emden-Weinert und Kreuter aus dem Jahr 1997 lieferte einen einfachen Beweis für das folgende Ergebnis, das viel stärker ist als das Ergebnis, das in Kristoffer Arnsfelt Hansens Antwort herausgestellt wurde:

Für jede gegebene rationale Zahl , der Hamilton - Operator Zyklus probem bleibt NP-vollständig selbst beschränkt , wenn auf bipartite planar n -eckiges Graphen der maximalen Grad 3 und Umfang ≥ n $0\le r <1/2$$n$$\ge n^r$ .

Das Manuskript enthält auch ähnliche Ergebnisse für andere Probleme wie Dominierendes Set, Max Cut, VFS usw.