Colourings of Graphs and Words

Extremal graph theory is concerned with the extreme values of a graph parameter over various classes of graphs. Randomised constructions have played a major role in extremal combinatorics. This phenomenon acted as a catalyst for the development of probabilistic combinatorics and the theory of random graphs as independent research areas. In the present thesis, we consider three graph parameters – anagram-chromatic number, rainbow connectivity and zero forcing number. Each of them is lower-bounded by a corresponding well-studied parameter (the Thue-chromatic number, diameter and minimum rank respectively). Our aim is to understand the hierarchy of graphs delineated by the parameter in consideration, and to highlight the role of random graphs as a surprising or close-to-optimal examples. Furthermore, we analyse a random graph process constrained to the König property. A graph is called König if the size of its maximum matching is equal to the order of its minimal vertex cover. We answer questions about the evolution and the final outcome of the process. A common feature of our proofs is that parts of them parallel classical problems concerning existence of relevant substructures in random graphs (Hamilton cycle, spanning tree, independent set, perfect matching). This allows us to rely on some well-known approaches. The second part of the thesis contains two Ramsey-type results. A catchphrase of Ramsey theory is that ‘any sufficiently large structure contains a well-organised substructure’. Let c be an edge-colouring of the complete n-vertex graph. The problem of finding properly coloured and rainbow Hamilton cycles in c was initiated in 1976 by Bollobás and Erdős and has been extensively studied since then. We study the problem in a more general hypergraph setting, giving sufficient local (resp. global) restrictions on the colourings which guarantee a properly coloured (resp. rainbow) copy of a given hypergraph G. We also look at multipartite analogues of these questions. In our final chapter, the ‘well-organised substructure’ of interest is a combinatorial line in [m]^n. The Hales–Jewett theorem states that for any m and r there exists an n such that any r-colouring of the elements of [m]^n contains a monochromatic combinatorial line. We look more closely at the obtained combinatorial line and prove tight results about the structure of its active coordinate set