Graph colouring and other stories

This thesis investigates a variety of different problems within the field of Graph Theory. Half of these problems relate to edge-colourings of graphs; the other half are concerned with H-colourings, reconstruction, and pursuit and evasion games. For graphs G and H, an H-colouring of G is a map ψ : V (G) → V (H) such that ij ∈ E(G) ⇒ ψ(i)ψ(j) ∈ E(H). The number of H-colourings of G is denoted by hom(G, H). In Chapter 2, we prove the following: for all graphs H and δ ≥ 3, there is a constant κ(δ, H) such that, if n ≥ κ(δ, H), the graph Kδ,n−δ maximises the number of H-colourings among all connected graphs with n vertices and minimum degree δ. This answers a question of Engbers [20]. We also disprove a conjecture of Engbers [19] concerning the graph G that maximises the number of H-colourings when the assumption of the connectivity of G is dropped. In the final part of Chapter 2, we let H be a graph with maximum degree k and show that, if H does not contain the complete looped graph on k vertices or Kk,k as a component and δ ≥ δ0(H), then the following holds: for n sufficiently large, the graph Kδ,n−δ maximises the number of H-colourings among all graphs on n vertices with minimum degree δ. This partially answers another question of Engbers [20]. In Chapter 3, we show that, in every 3-edge-colouring of the complete graph on N, there exists a partition of N into at most 2 connected monochromatic subgraphs. Erd˝os, Gy´arf´as and Pyber [22] attribute this result to Nagy and Szentmikl´ossy but, to our knowledge, a proof of it has never previously appeared in print. For every n ∈ N and k ≥ 2, it is known that every k-edge-colouring of the complete graph on n vertices contains a monochromatic connected component of order at least n k−1 . For k ≥ 3, it is known that the complete graph can be replaced by a graph G with δ(G) ≥ (1−εk)n for some constant εk. In Chapter 4, we show that the maximum possible value of ε3 is 1 6 . This disproves a conjecture of Gy´arfas and S´ark¨ozy [32]. Chapter 5 concerns edge-colourings of K~ N, the complete symmetric digraph on the positive integers. Answering a question of DeBiasio and McKenney [16], we construct a 2-edge-colouring of K~ N in which every monochromatic path has density 0. We then ask what happens if we restrict the length of monochromatic paths in one colour and show that, in every 2-edge-colouring that does not have a directed path with r edges in the first colour, there is directed path in the second colour with density at least 1 r . We also extend this result to more colours and prove a related stability result. The deck of a graph G is the multiset of (unlabelled) subgraphs {G−v : v ∈ V (G)}. The subgraphs G−v are referred to as the cards of G. Brown and Fenner [8] recently showed that, for n ≥ 29, the number of edges of a graph G can be computed from any deck missing 2 cards. In Chapter 6, we improve this result by showing that, for sufficiently large n, the number of edges can be computed from any deck missing at most 1 20 √ n cards. In Chapter 7, we consider the pursuit and evasion game, Cat and Mouse, which is played on a connected graph G with n vertices. The mouse moves to vertices m1, m2, . . . of G where mi is in the closed neighbourhood of mi−1 for i ≥ 2. The cat tests vertices c1, c2, . . . of G without restriction and is told whether the distance between ci and mi is at most the distance between ci−1 and mi−1. The mouse knows the cat’s strategy, but the cat does not know the mouse’s strategy. We show that the cat can determine the position of the mouse up to distance O( √ n) within finite time and that this bound is tight up to a constant factor. This disproves a conjecture of Dayanikli and Rautenbach [13]