# Is there a polynomial upper bound for number of holes over following class of graphs?

A hole is chordless cycle that length of the cycle is four or more.

In this post I asked: What is the maximum number of holes that a simple graph on n vertices can have?

Gil Kalai answered that there is no polynomial upper bound.

I need a polynomial upper bound for number of holes over following class of graphs: Graphs constructed from triangles such that no two triangles have more than one vertex in common. this graphs are not necessarily chordal, and may have holes.

May I hope for a polynomial upper bound for number of holes of such graphs?

• No. Subdivide each edge. This leaves a triangle-free graph with Poly($n$) vertices, and at least as many holes. Commented Jun 18, 2012 at 22:08
• Dear Andrew, we are not allowed subdivide edges. with triangles I mean $K_3$s.
– j.s.
Commented Jun 18, 2012 at 22:18
• If your graph be planar, your answer is easy by Euler formula. So you can think about the number of induced planar subgraphs of a graph. But, I didn't see any discussion about this Idea. Commented Jun 19, 2012 at 10:08
• Dear Shahrooz, I don't want number of faces. I want number of holes. After all, mentioned class of graphs contains some non-planar graphs.
– j.s.
Commented Jun 19, 2012 at 15:23