Re:Graph Coloring, or Proof by Crayon
by cperciva on Tuesday December 18, 2012 @01:28PM
(#4938769)
In case anyone is wondering: Paris is not 3-colourable. The proof is trivial, by looking at region 6 and its neighbours.
[ Parent
| on HN ]
Specifically:
6 - R
7 - G
1 - B
15 - B
16 - R
8 - Cannot be R G or B
Is there any way to translate between this rather visual proof and the degrees of 8's neighbouring vertices?
I tried to find if there was some theory behind it but all I could really find was "saturation degree".
Re:Graph Coloring, or Proof by Crayon
by ColinWright on Tuesday December 18, 2012 @05:45PM
(#4940061)
Not really, no. There are many, many results about when something is and is not three-colorable, but in the end, graph three coloring is NP-Complete.