Come for the quick hacks, stay for the epiphanies. | |
PerlMonks |
Re^2: Graph labeling problem (even n => n-1 colors)by LanX (Saint) |
on Feb 20, 2022 at 13:04 UTC ( [id://11141506]=note: print w/replies, xml ) | Need Help?? |
> I think you are dealing with factorials, so good luck with 50 factorial!! the wikipedia article shows an easy construction for an even n with n-1 colors. A picture showing the solution for K8 is given too. Basically, if you have a regular n-1 polygon plus it's center and connect all the nodes you'll have a Kn graph. Because of the regularity this graph has n-1 groups of (n-2)/2 parallel edges plus one perpendicular from the center m to the missing node. Parallel edges can never be adjacent. I tried to sketch it for K6 with a pentagram a b c d e and a center m
Of course it's hard to draw a regular pentagram in ASCI graphic, the display will also depend on your browser settings. But I hope it's obvious that symmetry leads to a solution with 5 colors here, which can be generalized to n even.
Cheers Rolf
In Section
Seekers of Perl Wisdom
|
|