Is there interest in an informal proof that Graph Vertex 3-Colouring is NPC?
A short time ago, in the discussion about Integer Linear Programming, I made a comment[0] about the relative hardness of Graph Vertex 3-Colouring (G3C), Satisfiability (SAT), and Integer Factoring (FAC). That got a few upvotes, but almost certainly just because it made clear and explicit the connections, and gathered together the ideas scattered through other replies.
But ... would anyone be interested in seeing a relatively complete proof that G3C is NPC?
https://news.ycombinator.com/item?id=44278725
Well ... I guess not.
I'd try to read it.
Thank you ... nice to have at least one person!
But with only one I've currently de-prioritised it. However, I do now have a mailing list and I'm more than happy to add you to it. I think I have two email addresses for you ... I'll ping you.