Timeline for "Nice" and "nasty" partitions in graphs
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 21, 2015 at 21:33 | comment | added | Will Brian | For $n = 6$, take the tree on vertices a,b,c,d,e,f with: a-c, b-c, c-d, d-e, d-f. Then $\{a,b,c\}$ is one half of a nasty partition, and $\{a,b,c\}$ is one half of a nice partition. By adding another vertex g with f-g, you can get a $7$-vertex graph that works. | |
| Jul 21, 2015 at 21:29 | comment | added | Will Brian | @GordonRoyle: Good question! This happens if and only if $n \geq 6$. To see that we need $n \geq 6$, suppose we have a "nice" partition of a graph on $4$ or $5$ vertices. We've already seen that nice partitions have at least two vertices in each partition set, so one set must have exactly two. To achieve niceness, there must be an edge between them and no edge to any vertex of the other partition piece. But then we lose connectedness, so we need $n \geq 6$. To see that $n \geq 6$ suffices, we only have to consider $n = 6,7$ (Ben Barber's answer does the rest). | |
| Jul 21, 2015 at 20:48 | comment | added | Gordon Royle | What if we ask for connected graphs with both types of partition? | |
| Jul 21, 2015 at 15:57 | comment | added | Will Brian | @GordonRoyle: Yes, that's a very succinct way of expressing the main idea here. | |
| Jul 21, 2015 at 15:46 | comment | added | Gordon Royle | Any bipartite graph has a nasty partition and any disconnected graph (no isolated vertices) has a nice partition... | |
| Jul 21, 2015 at 14:02 | vote | accept | Dominic van der Zypen | ||
| Jul 21, 2015 at 13:41 | history | answered | Will Brian | CC BY-SA 3.0 |