Crossposted from [MO](https://mathoverflow.net/questions/171493/polynomial-problems-in-graph-classes-defined-by-forbidden-induced-cyclic-subgrap).

Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).

> 
> Are there NP-hard graph problems that can be solved in
>  polynomial time for $C$ other than Clique and Clique
>  cover?
> 
> 
> 

If I remember correctly, this is impossible for
independent set (unless $P=NP$).

Search in graphclasses.org didn't find any.

A class for which Clique and Clique cover are
polynomial is [C5,C6,X164,X165,sunlet4,triangle-free](http://graphclasses.org/classes/gc_1022.html)

**Edit**

Negative for IS and Domination is in [this paper](http://www.sciencedirect.com/science/article/pii/S0304397505008327). Page 2, the graphs $S\_{i,j,k}$.
['https://cstheory.stackexchange.com/questions/24876', 'https://cstheory.stackexchange.com', 'https://cstheory.stackexchange.com/users/22348/']
I think there is a number of hard problems that become easy for triangle-free graphs; especially those deal directly with triangles such as Partition Into Triangles (Does G have a partition into triangles?). Other less trivial examples include:

* Stable Cutset Problem (Does G have an independent set S such that G-S is disconnected?). See:  *On stable sutsets in graphs,* Discrete Applied Math. 105 (2000) 39-50.
* Intersection Graph Basis (Is G the intersection graph of subsets of a k-element ground set?). See: Problem [GT59] in: Garey & Johnson, *Computers and Intractability: A Guide to the Theory of NP-Completeness.*
From the comment above: in [Stefan Kratsch, Pascal Schweitzer, Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs](http://arxiv.org/abs/1208.0142): GI is polynomial time (trivially) solvable for $(K\_s,I\_t)\text{-free}$ graphs, but also (less trivially) for $(K\_s,K\_{1,t})\text{-free}$ graphs.

**EDIT**: as noted in the comment, $K\_{1,t}$ doesn't contain a cycle (I read the introduction of the paper too quickly).

After thinking a little bit about it, it seems easy to prove the following (original?):

**NEGATIVE RESULT:** *for every finite set $\{H\_1,...H\_k\}$ in which every $H\_i$ contains a cycle, the problem of graph isomorphism (GI) restricted to the class $\mathcal{C}$ of $(H\_1,...,H\_k)\text{-free}$ graphs is GI-complete.*

*Proof:* Fixed a class of $(H\_1,...,H\_k)\text{-free}$ graphs in which each $H\_i$ contains a cycle, and given $G\_1,G\_2$, let $r$ be the length of the longest cycle of the $H\_i$s. Replace each edge $(u,v)$ of $G\_1,G\_2$ with a path of length $l = \lceil r/3 \rceil$ adding $l$ new nodes $(u,p\_1,p\_2,...,p\_l,v)$ (see figure below). By construction the new graphs $G'\_1, G'\_2$ are $(H\_1,...,H\_k)\text{-free}$ indeed the possible shortest cycles are those formed by a triangle that must have length $3\lceil r/3 \rceil + 3 > r$; and it is easy to prove that they are isomorphic if and only if the original $G\_1,G\_2$ are isomorphic.

![enter image description here](https://i.stack.imgur.com/IoPq3.png)

**Figure**: a graph $G\_1$ on the left, and the equivalent $(H\_1,...,H\_k)\text{-free}$ graph $G'\_1$ on the right (suppose that the longest cycle of the $H\_i$ has length $r=15$, so every edge of $G\_1$ is replaced with a path of length $l = 5$.

We can also extend the negative result to Hamiltonian cycle NPC problem, indeed it is an immediate corollary to the following (original?):

**Theorem**: for any $k \geq 3$, the Hamiltonian cycle problem remains NP-complete even if we the graph $G$ does not contain cycles of length $\leq k$.

*Proof* We know that the Hamiltonian cycle problem is NPC even on a planar directed graph $G$ with each node $v$ satisfying: $outdeg(v) + indeg(v) \leq 3$ (Papdimitriou and Vazirani, On Two Geometric Problems Related to the Travelling Salesman Problem).
We can transform the graph $G$ to an undirectde graph $G'$ simply adding a node on the incoming edge of nodes $v$ that have $indeg(v )=1$, and to the outgoing edge of nodes $v$ that have $indeg(v)=2$.
Then we can replace the nodes of $G'$ with the gadget in the figure below. It is easy to see that there are only two valid traversals (*zigzags*) that visit each node of the gadget exactly once (red and green paths in the figure): the gadgets cannot be traversed from top-to-bottom, otherwise the horizontal (incoming or outgoing) path would be cut out.
Furthermore we can place enough nodes on the vertical/horizontal segments of the gadgets, and extend the number of its zigzags, to ensure that no cycle of length $\geq k$ is possible in the gadget or in a triangle of 3 gadgets linked together. This assures that if the resulting graph $G''$ has an Hamiltonian cycle, then the original graph $G$ has also an Hamiltonian cycle (the converse is immediate by construction of the gadget).

![enter image description here](https://i.stack.imgur.com/uw6oT.png)

**Corollary:** Hamiltonian cycle and path problems remain NP-complete even if restricted to $(H\_1,...,H\_k)\text{-free}$ graphs, where every $H\_i$ contains a cycle.