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?

  • $\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 Jun 18 '12 at 22:08
  • $\begingroup$ Dear Andrew, we are not allowed subdivide edges. with triangles I mean $K_3$s. $\endgroup$ – j.s. Jun 18 '12 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 Janbaz Jun 19 '12 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. Jun 19 '12 at 15:23

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.