Timeline for What are constructions for induced $C_5$-free graphs?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 5, 2015 at 17:18 | history | edited | domotorp | CC BY-SA 3.0 |
added 200 characters in body
|
| Jul 5, 2015 at 12:40 | comment | added | joro | What about take any graph and subdivide all edges one or more times? | |
| Jul 5, 2015 at 11:44 | comment | added | Boris Bukh | Well, possibly one can request a very explicit construction that contains all C_5-free graphs of polylog size. Then duplicates trick won't work, but Paley graph would pass the test for the easier version. (One can even drop the "very explicit" part as long as the polylog is at least sqrt(log n), as even existence stops being obvious because there ought to be 2^{c*n^2} C_5-free graphs on n vertices.) | |
| Jul 5, 2015 at 11:41 | comment | added | domotorp | 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). | |
| Jul 5, 2015 at 11:18 | comment | added | Boris Bukh | 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). | |
| Jul 5, 2015 at 11:09 | comment | added | Boris Bukh | 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. | |
| Jul 5, 2015 at 11:06 | comment | added | domotorp | 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. | |
| Jul 5, 2015 at 10:55 | comment | added | Boris Bukh | 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? | |
| Jul 5, 2015 at 9:27 | history | asked | domotorp | CC BY-SA 3.0 |