Problems With The ERM

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

See the page that discusses what makes a graph difficult to colour.

If we assume (and this is a big assumption) that the difficulty is tightly related to the transition from many colourings to there being a unique colouring, then we can see that the "peak" in the ERM will be broad.

As we throw in edges the graph becomes more and more connected, but there are always some "stragglers," some vertices that are connected to only one of the other two colour classes. Until each vertex is "well connected" there are trivially multiple colourings

However, consider the phase shortly before the colouring is unique. There will be a comparatively small number of vertices that are only connected to one of the other colour classes, but if we "shave the graph" and get rid of these few hairy bits, what's left is probably uniquely colourable, and has been for some time.

So there is a sort of "core graph" that has been uniquely colourable, and therefore made the graph difficult to colour, even though the full graph is not uniquely colourable. So the difficulty of colouring and the transition to uniqueness of colouring are separated by these hairy bits.

The Matching-by-Matching model is designed to get around this. Mostly.