MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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. – Andrew D. King Jun 18 2012 at 22:08 Dear Andrew, we are not allowed subdivide edges. with triangles I mean $K_3$s. – b.a 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. – Shahrooz 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. – b.a Jun 19 2012 at 15:23