Skip to main content
added 200 characters in body
Source Link
domotorp
  • 19.1k
  • 3
  • 59
  • 128

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, other induced cycles and so on. What are some non-trivial constructions for such graphs? I suppose the question also makes sense for other graphs.

Just to clarify, by construction I mean something very explicit, like the vertices correspond to length $n$ zero-one sequences and we connect two vertices if their inner product is a prime number.

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, other induced cycles and so on. What are some non-trivial constructions for such graphs? I suppose the question also makes sense for other graphs.

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, other induced cycles and so on. What are some non-trivial constructions for such graphs? I suppose the question also makes sense for other graphs.

Just to clarify, by construction I mean something very explicit, like the vertices correspond to length $n$ zero-one sequences and we connect two vertices if their inner product is a prime number.

Source Link
domotorp
  • 19.1k
  • 3
  • 59
  • 128

What are constructions for induced $C_5$-free graphs?

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, other induced cycles and so on. What are some non-trivial constructions for such graphs? I suppose the question also makes sense for other graphs.