New blog post: Triply-Hamiltonian edge colorings

In, Mark Jason Dominus (@mjd) observed that the regular dodecahedron can have its edges properly colored with three colors so that every two colors form a Hamiltonian cycle. In this post, I survey constructions for more graphs like this, and prove that no planar bipartite graph can have a coloring like this.

· · Web · 1 · 4 · 3

@11011110 @mjd that three-colouring sounds interesting, but I can only see two colours in the first diagram of your post. Are two of the colours red and green? The thick blue/yellow/black in the second diagram is easier to see, for me.

@christianp @11011110 Yes, the colors came out very unclear, even with the different dotting patterns. I will try to fix it later. Meantime, the image is SVG, so you should be able to make it clearer by enlarging it.

@mjd @11011110 it looks like the kinds of edge are: solid black, blue dashes, blue dots.
I have protanopia, which is one of the kinds of colourblindness commonly called 'red-green'.
Using different colours makes sense, since it's a colouring problem, but getting even three colours that are good for everyone is tricky. Different patterns is the safest way to go, as you've done.

@christianp Can you please send me swatches or RGB triples for at least six colors that you find easily distinguishable?

@christianp Oh, and I just realized that the colored circles in the second diagram are not all going to be distinguishable. I will fix that.

@christianp If you don't mind, can you tell me which of these you prefer? (Please view at full size.)

@mjd in the first one, the circles are easily distinguished but hard to relate to the edges. In the second, it'd be much easier to see if the circles were filled with the pattern, instead of just around the edges

@christianp @mjd @11011110 I'd just like to point out that there do exist some well-tested resources for colourblind-friendly colour palettes. The most commonly recommended one is ColorBrewer ( by Cynthia Brewer: pick "qualitative" and "colorblind safe". I'm also partial to Paul Tol's colour schemes (, which I find more aesthetically appealing. That said, I'm not colourblind, so I can't personally vouch for their effectiveness in that respect.

@narain @mjd @11011110 ColorBrewer is good. Notice that it's only got one qualitative colour scheme for use with 4 data classes. You really can't do any more than that - colourblindness sucks!

@narain @mjd @11011110 that page of Paul Tol's is a really good reference that I hadn't seen before - thanks!

@christianp Are you red-green color blind? If so I would be grateful for your advice on any of my diagrams. I try to keep it in mind when I am designing, but I don't really know how well I am doing. But that dodecahedron diagram was a failure for everyone, including me.

@christianp @mjd My first diagram is blue/pink (alternating around the outside) and green (in the middle). The second (the one you say is blue/yellow/black) is actually blue/yellow/red. Maybe I should switch to those colors throughout?

Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!