Cliques, colours and clusters

Contains fulltext : 191382.pdf (publisher's version ) (Open Access)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ás-Eldridge-Catlin conjecture, for graphs of bounded codegree. This implies an upperbound on the equitable chromatic number. Second, we prove that every triangle-free graph G has strong clique number at most 5/4* Delta(G)^2. This constitutes the clique version of the infamous Erdös-Nesetril conjecture on colouring the square of a line graph. Third, we prove that -conditional on the Erdös-Nesetril conjecture for multigraphs being true- it also holds that the square of any claw-free 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 plane-embedded 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 nearest-neighbour 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ás-Eldridge-Catlin conjecture, for graphs of bounded codegree. This implies an upperbound on the equitable chromatic number. Second, we prove that every triangle-free graph G has strong clique number at most 5/4* Delta(G)^2. This constitutes the clique version of the infamous Erdös-Nesetril conjecture on colouring the square of a line graph. Third, we prove that -conditional on the Erdös-Nesetril conjecture for multigraphs being true- it also holds that the square of any claw-free 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 plane-embedded 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 nearest-neighbour 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.Radboud University, 27 juni 2018Promotor : Cator, E. Co-promotor : Kang, R.J.129 p