Timeline for "Nice" and "nasty" partitions in graphs
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 21, 2015 at 14:02 | vote | accept | Dominic van der Zypen | ||
| Jul 21, 2015 at 13:41 | answer | added | Will Brian | timeline score: 3 | |
| Jul 21, 2015 at 13:02 | comment | added | Ben Barber | More generally, given examples on $n_1$ vertices and $n_2$ vertices you can find an example on $n_1 + n_2$ vertices by taking a vertex-disjoint union. So it remains only to check whether such graphs exist for small odd $n$. | |
| Jul 21, 2015 at 11:21 | answer | added | Ben Barber | timeline score: 4 | |
| Jul 21, 2015 at 10:59 | comment | added | Gordon Royle | I think we can do all even numbers $2k \geq 4$ by taking $k$ disjoint edges. The partition that takes one vertex from each edge is nasty as each vertex has 0 neighbours in its own part, and 1 in the other. But the partition that takes some edges in one part and the remaining edges in the other part is nice, because each vertex has 1 neighbour in its own part and 0 in the other. | |
| Jul 21, 2015 at 9:20 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |