Timeline for Can a 3-regular non-1-planar graph be constructed?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 25, 2023 at 11:32 | vote | accept | Licheng Zhang | ||
| Feb 23, 2023 at 16:49 | comment | added | user44143 | That helps, it wasn’t obvious before. It might also help to add a couple words to the proof on this. | |
| Feb 23, 2023 at 16:39 | comment | added | Boris Bukh | @MattF. $G$ is a random $3$-regular graph, and the proof shows that it works with high probability. The only step of the proof that uses randomness is the expansion property, so the proof in fact works for every $3$-regular expander (with an appropriate condition on the expansion constant in terms of $n$, which can be worked out from the proof). | |
| Feb 23, 2023 at 16:29 | comment | added | Boris Bukh | @MattF. Of course not, a disjoint union of $4$-cliques is planar. | |
| Feb 23, 2023 at 16:24 | comment | added | user44143 | Does this show that every sufficiently large $3$-regular graph is not $t$-planar? The word "random" suggests "asymptotically almost every" instead. | |
| Feb 22, 2023 at 18:47 | history | answered | Boris Bukh | CC BY-SA 4.0 |