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?

$\endgroup$
4
  • $\begingroup$ No. Subdivide each edge. This leaves a triangle-free graph with Poly($n$) vertices, and at least as many holes. $\endgroup$ 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.
    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
    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.
    Jun 19, 2012 at 15:23

1 Answer 1

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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