4 ms·
Let v be a vertex in a N-dimensional hypercube. Assume it's colored C. It has N neighbors, which must be colored ~C if we're using 2 colors. If you change v to
by MichaelBurge 6y ago
Let v be a vertex in a N-dimensional hypercube. Assume it's colored C. It has N neighbors, which must be colored ~C if we're using 2 colors.
If you change v to ~C, v now has N neighbors with the same color. This improves on the √N you're giving.
What did I misunderstand?
- LolWolf 6y agoWell, turns out you’re completely right and I fucked up my reduction (quite badly it seems)! Alas, it also turns out I can’t edit nor delete the post, so, hopefully people get this far down the thread and read this :)