Abstract

Paul Erdős proved that there exist graphs with no short cycles requiring arbitrary many colours to colour their vertices so that no two adjacent vertices have the same colour. Unfortunately, the proof does not explicitly construct such graphs. A well known example sheet problem asks for an example in the simplest case, where we ban triangles—cycles of length 3. Such examples seem hard to find, and tend to contain many cycles of length 4. I shall discuss a solution to this problem by Nesetril and Rodl using their method of “amalgamation” which, while it is more complicated than other solutions, also allows us to ban longer cycles (and can do much more besides). No prior knowledge of graph theory is required.