Timeline for Does every graph admit an embedding such that identically-colored edges do not cross?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 6, 2023 at 16:48 | vote | accept | Tjaden Hess | ||
| Dec 4, 2023 at 13:17 | comment | added | bof | Ramsey's theorem tells us that for any fixed number of colors a sufficiently large complete graph will contain a monochromatic $K_5$. | |
| Dec 4, 2023 at 10:29 | answer | added | Tony Huynh | timeline score: 4 | |
| Dec 4, 2023 at 4:13 | comment | added | Jukka Kohonen | If your problem is solved, you could answer your own question and accept the answer, so that it does not stay "unanswered". | |
| Dec 4, 2023 at 1:12 | comment | added | Tjaden Hess | Ah yes, thinking of it as the union of planar subgraphs does make the structure of the problem much clearer. Seems obvious now, but thank you for the tip | |
| Dec 4, 2023 at 1:10 | comment | added | Tony Huynh | I think the minimum number of colours is sometimes called geometric thickness. | |
| Dec 4, 2023 at 0:54 | comment | added | Jukka Kohonen | Seems related to graph thickness? | |
| Dec 4, 2023 at 0:49 | comment | added | Tony Huynh | It is not always possible with two colours since an $n$-vertex planar graph has at most $3n-6$ edges, and the red subgraph and blue subgraph are both planar graphs. So, any $n$-vertex graph with at least $6n-11$ edges is a counterexample. | |
| S Dec 4, 2023 at 0:34 | review | First questions | |||
| Dec 4, 2023 at 1:08 | |||||
| S Dec 4, 2023 at 0:34 | history | asked | Tjaden Hess | CC BY-SA 4.0 |