Skip to main content
MathOverflow

Return to Question

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

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

In this postthis 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?

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?

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?

deleted 8 characters in body
Source Link
j.s.
j.s.
  • 519
  • 2
  • 11

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 class of graphs isare not necessarily chordal, and may have holes.

May I hope for a polynomial upper bound for number of holes of such 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 class of graphs is not necessarily chordal, and may have holes.

May I hope for a polynomial upper bound for number of holes of such 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?

Source Link
j.s.
j.s.
  • 519
  • 2
  • 11

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 class of graphs is not necessarily chordal, and may have holes.

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