Is there interest in an informal proof that Graph Vertex 3-Colouring is NPC?

1•ColinWright•7mo ago

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

Comments

ColinWright•7mo ago

Well ... I guess not.

gus_massa•7mo ago

I'd try to read it.

ColinWright•7mo ago

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.

Study confirms experience beats youthful enthusiasm

The Big Hunger by Walter J Miller, Jr. (1952)

The Genus Amanita

We have broken SHA-1 in practice

Ask HN: Was my first management job bad, or is this what management is like?

Ask HN: How to Reduce Time Spent Crimping?

KV Cache Transform Coding for Compact Storage in LLM Inference

A quantitative, multimodal wearable bioelectronic device for stress assessment

Why Big Tech Is Throwing Cash into India in Quest for AI Supremacy

How to shoot yourself in the foot – 2026 edition

Eight More Months of Agents

From Human Thought to Machine Coordination

The new X API pricing must be a joke

Show HN: RMA Dashboard fast SAST results for monorepos (SARIF and triage)

Show HN: Source code graphRAG for Java/Kotlin development based on jQAssistant

Python Only Has One Real Competitor

Tmux to Zellij (and Back)

Ask HN: How are you using specialized agents to accelerate your work?

Passing user_id through 6 services? OTel Baggage fixes this

DavMail Pop/IMAP/SMTP/Caldav/Carddav/LDAP Exchange Gateway

Visual data modelling in the browser (open source)

Show HN: Tharos – CLI to find and autofix security bugs using local LLMs

Oddly Simple GUI Programs

The New Playbook for Leaders [pdf]

Interactive Unboxing of J Dilla's Donuts

OneCourt helps blind and low-vision fans to track Super Bowl live

Rudolf Vrba

Autism Incidence in Girls and Boys May Be Nearly Equal, Study Suggests

Wellness Hotels Discovery Application

NASA delays moon rocket launch by a month after fuel leaks during test