Beefy Boxes and Bandwidth Generously Provided by pair Networks
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??


in reply to Re: Graph labeling problem
in thread Graph labeling problem

> 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

d | e---------c m a-----b

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
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11141506]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (5)
As of 2024-03-28 16:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found