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/']
Here are some additional examples to Mon Tag's answer :

* The Disconnected Cutset problem (Does $G$ admit a set of vertices $S$ such that $G-S$ and the subgraph of $G$ induced by $S$ are disconnected) is NP-complete (see [here](http://dx.doi.org/10.1007/978-3-642-23786-7_43)). It is easy to see that this problem is polynomially solvable for triangle-free graphs (hence also the Stable Cutset problem as mentioned by Mon Tag).
* Recognizing triangular line graphs is NP-complete (see [here](http://www.sciencedirect.com/science/article/pii/S0012365X11005449)), It is also 
easy to see that this problem becomes polynomially for triangle-free input graphs.
* Computing the maximum connected matching is hard (see [here](http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1206). 
A matching is connected if, for any pair of the matching edges, there is another edge of the graph incident to both of them). 
It can be proved that this problem is polynomially solvable for $(C\_3, C\_4, C\_5)$-free graphs.
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.