1
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ I do not understand the question: Enumerate all graphs that contain no induced C_5-free graph. Then take a disjoint union of these. Or you ask whether the class of C_5-free graphs has the amalgamation property? $\endgroup$
    – Boris Bukh
    Commented Jul 5, 2015 at 10:55
  • $\begingroup$ Yours is certainly a valid construction, but I'm looking for something more concrete, for a graph that can be described with some simple operations using which it is easy to check whether there is an edge between two vertices and so on, like a Paley graph. $\endgroup$
    – domotorp
    Commented Jul 5, 2015 at 11:06
  • $\begingroup$ Ah, you seek a very explicit (in a sense of polylog algorithm to tell if edge is ain a graph) construction? I am not sure that the disjoint construction cannot be made into that form; instead of one copy of each graph, one duplicates each graph a huge number of times to buy oneself time for computation. $\endgroup$
    – Boris Bukh
    Commented Jul 5, 2015 at 11:09
  • $\begingroup$ Intuitively, I think I see what you want, but it would be very useful to make the question sufficiently precise so that one can unambigously tell what constitutes an answer. In particular, it would permit proving a negative result (non-existence). $\endgroup$
    – Boris Bukh
    Commented Jul 5, 2015 at 11:18
  • $\begingroup$ I'm sure that putting enough duplicates would satisfy whatever property I ask for. I'm not sure how to make my question precise. Maybe it's best to consider it asking for a big list of possible constructions (yours can be number one). $\endgroup$
    – domotorp
    Commented Jul 5, 2015 at 11:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .