<p>This unpublished <a href="http://www.or.uni-bonn.de/~hougardy/paper/girthall.pdf">manuscript</a> by Hougardy, Emden-Weinert and Kreuter in <strong>1997</strong> 
provided a simple proof for the following result which is much stronger than the result pointed out in 
Kristoffer Arnsfelt Hansen's answer:</p>

<blockquote>
  <p>For any given rational number $0\le r &lt;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$.</p>
</blockquote>

<p>The manuscript contains also similar results for other problems such as Dominating set, Max cut, VFS, etc.  </p>

CC BY-SA 3.0
2014-06-17T17:00:20.763Z
Ok, thanks! I forgot to mention that my proof works for planar undirected bipartite graphs of max-degree 3 ... so the Hourgardy et al. paper is stronger ... but not *much* stronger :-) :-). I'll probably accept Kristoffer's answer because he posted it first.
Marzio De Biasi
CC BY-SA 3.0
2014-06-17T21:26:00.067Z
@MarzioDeBiasi, I think the strongness is about the size of a girth. your proof is about fixed number, accepted answer is for some f(n) which is less than sqrt and this answer is more general than all of them. (IMHO restriction to the graph is not very important here)
Saeed
CC BY-SA 3.0
2014-06-18T09:08:00.723Z
The paper contains other NP-hard problems, it will be an answer to the linked question about cyclic graphs.
joro
CC BY-SA 3.0
2014-06-17T16:39:31.527Z
2014-06-17T18:05:47.110Z
2014-06-17T18:05:47.110Z
vb le
<p>The result is stated in the paper <a href="http://dx.doi.org/10.1016/j.endm.2007.07.090">Two New Classes of Hamiltonian Graphs </a> by Arkin, Mitchell and Polinshchuk.</p>

CC BY-SA 3.0
2014-06-17T15:35:20.280Z
2014-06-17T15:35:20.280Z
Kristoffer Arnsfelt Hansen
<p>While answering this <a href="https://cstheory.stackexchange.com/a/24882/3247">question on cstheory</a>, I (informally) proved on the fly the following theorem:</p>

<p><strong>Theorem</strong>: 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$.</p>

<p>It seems very unlikely that it has not already appeared somewhere.<br>
But it allows to settle many Hamiltonian cycle/path problems on graphclasses.org that are marked as "Unknown to ISGCI" (see for example <a href="http://graphclasses.org/classes/gc_911.html" rel="nofollow noreferrer">this one</a>); 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.</p>

<blockquote>
  <p>Can you give me a reference of the paper/book where it appeared?</p>
</blockquote>

<p>(then I'll contact people at graphclasses.org)</p>

CC BY-SA 3.0
2014-06-18T08:02:30.150Z
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
CC BY-SA 3.0
2014-06-18T08:42:33.443Z
@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
CC BY-SA 3.0
2014-06-18T09:04:44.370Z
I heard they don't update the database very often and reply with "thanks" after updating the DB and they are quite responsive.
joro
CC BY-SA 3.0
2014-06-23T07:27:20.730Z
@joro: I think they updated the database (they are very collaborative and polite)
Marzio De Biasi
<reference-request><np-hardness>
Hamiltonian cycle on graphs without small cycles
Marzio De Biasi
# Hamiltonian cycle on graphs without small cycles

(Asked by: username_0 on 2014-06-17)

While answering this [question on cstheory](https://cstheory.stackexchange.com/a/24882/3247), 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](http://graphclasses.org/classes/gc_911.html)); 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)

**Tags:** reference-request, np-hardness

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1: 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.  
> **username_1**: I heard they don't update the database very often and reply with "thanks" after updating the DB and they are quite responsive.  
> **username_0**: @username_1: I think they updated the database (they are very collaborative and polite)  

---

## 2 answers

### Answer by username_4 on 2014-06-17. Score: 13 | Accepted answer

The result is stated in the paper [Two New Classes of Hamiltonian Graphs](http://dx.doi.org/10.1016/j.endm.2007.07.090)  by Arkin, Mitchell and Polinshchuk.


---

### Answer by username_2 on 2014-06-17. Score: 26

This unpublished [manuscript](http://www.or.uni-bonn.de/~hougardy/paper/girthall.pdf) by Hougardy, Emden-Weinert and Kreuter in **1997**
provided a simple proof for the following result which is much stronger than the result pointed out in
username_4's answer:

> 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$.

The manuscript contains also similar results for other problems such as Dominating set, Max cut, VFS, etc.

> **Comments:**
> **username_0**: Ok, thanks! I forgot to mention that my proof works for planar undirected bipartite graphs of max-degree 3 ... so the Hourgardy et al. paper is stronger ... but not *much* stronger :-) :-). I'll probably accept Kristoffer's answer because he posted it first.  
> **username_3**: @MarzioDeBiasi, I think the strongness is about the size of a girth. your proof is about fixed number, accepted answer is for some f(n) which is less than sqrt and this answer is more general than all of them. (IMHO restriction to the graph is not very important here)  
> **username_1**: The paper contains other NP-hard problems, it will be an answer to the linked question about cyclic graphs.  

---

