2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ No. Subdivide each edge. This leaves a triangle-free graph with Poly($n$) vertices, and at least as many holes. $\endgroup$
    – Andrew D. King
    Commented Jun 18, 2012 at 22:08
  • $\begingroup$ Dear Andrew, we are not allowed subdivide edges. with triangles I mean $K_3$s. $\endgroup$
    – j.s.
    Commented Jun 18, 2012 at 22:18
  • $\begingroup$ 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. $\endgroup$
    – Shahrooz
    Commented Jun 19, 2012 at 10:08
  • $\begingroup$ 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. $\endgroup$
    – j.s.
    Commented Jun 19, 2012 at 15:23

1 Answer 1

Reset to default
5
$\begingroup$

Gil Kalai's example has no triangles - the smallest cycle has length 4. So glue a triangle to each edge of his graph. (Add a vertex, and connect it to both vertices of the edge). This graph is then constructed of triangles, but no two triangles share an edge. (and it's simple, so no two triangles share two points) None of the holes have gained chords.

Thus, it is still a counterexample.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .