This is probably a silly question but I have a definition in front of me that says:

A graph G is k-colourable if the nodes of G can be coloured using no
more than k colours.

Does a colourable graph need to be connected? I think it does as we could have an arbitrary amount of singleton nodes.

  • $\begingroup$ The definition you recall seems somewhat incomplete as you do not mention any conditio on the clorouring. (Perhaps this is implict in the "coloured" in the source you quote.) $\endgroup$ – quid Feb 20 '15 at 14:41

It is not necessary it is connected. However, a graph is $k$-colourable if and only if each of its connected components is. Thus, it does not change that much.

For your specific objection: singleton nodes are a non-issue for colouring; you want different colours for adjacent notes, isolated ones can just be coloured however you want.

  • $\begingroup$ I see, I wasn't sure about the singleton nodes. Thanks $\endgroup$ – Nubcake Feb 20 '15 at 14:42
  • $\begingroup$ You are welcome. Yes sometimes such cornercase are strange. However also note that even if it were different it would not exclude the notion would make sense. Say you have a million isoloated nodes and you would need a different colour for each, you just would have to admit enough colours. $\endgroup$ – quid Feb 20 '15 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.