3 ms·

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

by Cogito 7y ago

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?

OscarCunningham 7y ago
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. https://standardwisdom.com/softwarejournal/2012/07/a-graph-that-requires-5-colors-but-does-not-contain-k5-complete-graph-on-5-vertices/ https://standardwisdom.com/softwarejournal/2012/07/a-graph-t...
- Cogito 7y ago
  Thanks, that's a really great example. It definitely feels non trivial to come up with an example.
intuitionist 7y ago
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.)
- Cogito 7y ago
  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.
  - intuitionist 7y ago
    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.

by Cogito 7y ago

OscarCunningham 7y ago

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. https://standardwisdom.com/softwarejournal/2012/07/a-graph-that-requires-5-colors-but-does-not-contain-k5-complete-graph-on-5-vertices/ https://standardwisdom.com/softwarejournal/2012/07/a-graph-t...

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

intuitionist 7y ago

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.)

Cogito 7y ago
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.
- intuitionist 7y ago
  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.