Timeline for Cubic graphs, unfriendly partitions and hamiltonicity
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 3 at 3:51 | comment | added | Gordon Royle | I don't understand where you get your numbers from. Starting from 4 vertices, there are 1, 1, 2, 5, 14, 50, 233, 1249, 7595, 49566, 339722 planar cubic graphs as per OEIS oeis.org/A000109. How do you get 1.4 million? | |
| Feb 1, 2017 at 12:52 | comment | added | Louis Esperet | You probably need to add "planar" or "2-edge-connected" in your question, otherwise the answer is negative. Consider two copies of $K_{3,3}$, remove an edge $uv$ in the first copy, and an edge $xy$ in the second copy. Then add two vertices $w$ and $z$, joined by an edge, such that $w$ is adjacent to $u$ and $v$, and $z$ is adjacent to $x$ and $y$. It is not difficult to show that an unfriendly partition is necessarily a proper 2-coloring, and is therefore balanced. You should maybe look at this paper related to your question arxiv.org/abs/1504.03500 | |
| Jan 31, 2017 at 17:42 | history | asked | Jernej | CC BY-SA 3.0 |