Hacker News new | past | comments | ask | show | jobs | submit login

Is it true to say that a graph can be coloured by k colours if and only if the largest fully connected subgraph has k or fewer members?

For example, is saying a planar graph can always be coloured by 4 colours the same as saying a planar graph can never have more than 4 nodes that are all connected to each other?

They're not quite the same. Certainly if there are five vertices all connected to each other then the graph can't be four-coloured. But the converse isn't true.


Thanks, that's a really great example. It definitely feels non trivial to come up with an example.

No, in fact there are graphs of arbitrary chromatic number that don’t even contain a triangle. It’s true, and quite easy to prove, that a planar graph can’t contain a complete subgraph on 5 vertices. But this isn’t sufficient to prove the four-color theorem.

There is a slight modification of the statement that may be correct; if you replace the condition of having a complete subgraph with that of having a complete minor, this is a very famous open problem called the Hadwiger conjecture. (It’s known to be true for the case n=5, i.e. every 5-chromatic graph has a K_5 minor.)

To confirm I understand (and I think this is where I was at originally):

If a graph contains K_5 then it requires at least 5 colours to colour, but if a graph does not contain K_5 then it might still require 5 colours.

The example given by OscarCunningham is a great one.

Right—as mathematicians say, having a K_n subgraph is a sufficient but not necessary condition for having a chromatic number of at least n. Hadwiger’s conjecture goes the other way, stating that having a K_n minor is a necessary but not sufficient condition for having a chromatic number of at least n.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact