Introduction

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

It's generally believed that for and NPC problem the proportion of difficult instances goes to zero. However, for applications such as Public-Key Cryptography we would like to base the system on a problem that is know to be NPC, and to do that we have to be able to generate difficult instances. (See the page on RSA for a brief discussion of this.)

We know that G3C (Graph Three-Colouring) is NPC, but we also know that when a graph has very few edges it's trivial to colour, and when it has many edges it is again trivial to colour. So to have a hard instance of G3C the number of edges must be "just right."

We call this the Erdos-Renyi Model

Dominic Welsh has done some work on this, investigating a random-graph model of a 3-colourable graph, and found that as the number of edges passes through a certain area the graph becomes difficult to colour, and then easy again. He used a graph-colouring computer program as a measure the difficulty of a particular instance.

However, as the parameter in the ERM goes through its range, the difficulty peak is fairly broad. It would seem that while the ERM gives us a way of looking at the difficulty of graph colouring, it does not pin down the real reason why one graph is difficult to colour while another isn't, not how to create difficult-to-colour graphs.

In this document we investigate an alternative model to see if we can get a sharper peak, homing in more tightly on the question of exactly which graphs are difficult to three-colour. We also look at why the ERM does not accomplish what we want, and why the new model doesn't have the same problems.

• Graph Colouring Algorithms
• What makes a graph difficult to colour?
• Problems with the ERM
• The Matching-by-Matching model