## Cliques, colours and clusters

##### Publication year

2018##### Author(s)

##### Publisher

[S.l. : s.n.]

##### Number of pages

129 p.

##### Annotation

Radboud University, 27 juni 2018

Promotor : Cator, E.
Co-promotor : Kang, R.J.

##### Publication type

Dissertation

Display more detailsDisplay less details

##### Organization

Mathematics

##### Subject

Mathematics##### 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á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.

##### This item appears in the following Collection(s)

- Academic publications [190284]
- Dissertations [11377]
- Electronic publications [90739]
- Faculty of Science [29489]
- Open Access publications [59963]

Upload full text

Use your RU credentials (u/z-number and password) tolog in with SURFconextto upload a file for processing by the repository team.