Abstract:

In this thesis, we derive several results concerning extremal graph theory and probability theory, focusing particularly on proper colourings of graphs.
First, we prove a special case of the BollobásEldridgeCatlin conjecture, for graphs of bounded codegree. This implies an upperbound on the equitable chromatic number.
Second, we prove that every trianglefree graph G has strong clique number at most 5/4* Delta(G)^2. This constitutes the clique version of the infamous ErdösNesetril conjecture on colouring the square of a line graph.
Third, we prove that conditional on the ErdösNesetril conjecture for multigraphs being true it also holds that the square of any clawfree graph G can be coloured with at most 5/4* omega(G)^2.
Fourth, we consider the intersection graph G(F) of a collection F of planeembedded Jordan regions that pairwise have at most one point in common. We show that the chromatic number of G(F) is at most 1 plus its clique number (provided that the clique number is at least 490). We similarly investigate the intersection graph of certain families of Jordan curves.
Fifth, we show that the chromatic number of a graph is at most the average of the degeneracy and the strong immersion number, rounded upwards.
Sixth and finally, we prove that the mass dimension of the Incipient Infinite Cluster (IIC) for nearestneighbour bond percolation on Z^d (for d large enough) is 4, with probability one. The volume growth exponent of the IIC is 2, with probability 1.
In this thesis, we derive several results concerning extremal graph theory and probability theory, focusing particularly on proper colourings of graphs. First, we prove a special case of the BollobásEldridgeCatlin conjecture, for graphs of bounded codegree. This implies an upperbound on the equitable chromatic number. Second, we prove that every trianglefree graph G has strong clique number at most 5/4* Delta(G)^2. This constitutes the clique version of the infamous ErdösNesetril conjecture on colouring the square of a line graph. Third, we prove that conditional on the ErdösNesetril conjecture for multigraphs being true it also holds that the square of any clawfree graph G can be coloured with at most 5/4* omega(G)^2. Fourth, we consider the intersection graph G(F) of a collection F of planeembedded Jordan regions that pairwise have at most one point in common. We show that the chromatic number of G(F) is at most 1 plus its clique number (provided that the clique number is at least 490). We similarly investigate the intersection graph of certain families of Jordan curves. Fifth, we show that the chromatic number of a graph is at most the average of the degeneracy and the strong immersion number, rounded upwards. Sixth and finally, we prove that the mass dimension of the Incipient Infinite Cluster (IIC) for nearestneighbour bond percolation on Z^d (for d large enough) is 4, with probability one. The volume growth exponent of the IIC is 2, with probability 1.
