What Makes A Graph Difficult To Colour

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

Consider a 3-colourable graph. When we colour it with three colours we divide it into colour classes, so we can see that the graph is tri-partite.

Suppose that between each colour class in this given colouring there are many, many edges. Then when we start colouring a few vertices, many other colours are forced. At each stage we have few choices, and those choices that are wrong are quickly shown to be so. As a result, a graph with many edges between the colour classes is easy to colour.

Suppose now that there are only a few edges between the colour classes. Now we can make a mistake and it won't become evident for quite some time. However, it is likely that a mistake won't actually matter, because if there are sufficiently few edges there will be many colourings. We could choose the "wrong" colour for a vertex, only to have it lead to a colouring other than the default.

Thus having very few edges makes the graph easy to colour.

So the graph is difficult to colour when the number of edges is just right to make it so.

The above argument gives rise naturally to an interesting speculation. When there are very few edges there are lots of colourings, and when there are many edges there is (probably) only one. So as we add edges two things happen:

• We pass through an area of "difficult to colour" graphs;
• The graph transitions from having many colourings to having only one.