Given a graph G and a proper vertex r-colouring c : V(G) ! [r], we can draw an auxiliary directed graph Ac on vertex set [r] by putting, for each i 6= j, an arc 􀀀!i j if there is a vertex in c􀀀1(i) which has no neighbours in c􀀀1(j) (in other words, if there is a vertex with colour i

which we could recolour to j and still have a proper colouring). An equitable r-colouring of G is a proper vertex r-colouring c : V(G) ! [r] such that c􀀀1(i) = 

c􀀀1(j) 1 for each i, j 2 [r] (in other words, any two colour classes differ in size by at most one). Suppose from now on that D(G)  k, for some integer k  1, and that c is a proper vertex r-colouring of G such that 1  c􀀀1(1) 




c􀀀1(r) .

(a) What is the minimum number of arcs in Ac leaving each i? (Your answer should not depend on G or i, but only on r and k, and you must both give an example (G, c, i) showing that you can have so few arcs leaving i, and also a proof that for any G, c and i you cannot have fewer) (b) What is the minimum number of arcs entering 1? How does the answer change if in

addition you are told that 􀀀! n1 is not in Ac, and

c􀀀1(n) > c􀀀1(1)

? In both cases, give both a lower bound on the minimum number and also an example showing it is best possible. (c) Suppose that r  2k. Prove that there is a directed path in Ac from a largest to a smallest

colour class. Deduce that G has an equitable r-colouring. (d) Give a polynomial-time algorithm which, on input a graph G with maximum degree k and any r  2k, returns an equitable r-colouring. Prove your algorithm is correct and has polynomial running time. (e) (Bonus Points) Prove that if k  2 then G also has an equitable (2k 􀀀 1)-colouring. The distance square G(2) of G is the graph on V(G) with xy 2 E 􀀀 G(2)

if either xy 2 E(G) or x 6= y and xz and yz are in E(G) for some z 2 V(G) (In other words, xy is in E 􀀀 G(2)

if x and y are at distance one or two from each other in G).

(f) If D(G)  k, how large can D 􀀀 G(2)

be? Give an upper bound and an example which shows it is best possible. If c is a proper vertex r-colouring of G(2), then what structure does c reveal in G? (In other words, what can we say about the edges of G within one, or between two, colour classes of c?)

Given two graphs G and H, we say f is an embedding of G into H if f : V(G) ! V(H) is injective (so f(x) 6= f(y) whenever x 6= y), and for all edges xy of G, the pair f(x)f(y) is an edge of H. (Note that this is not an 'if and only if' condition, so if xy is not an edge of G then f(x)f(y) may or may not be an edge of H). If there exists an embedding of G into H, we say

H contains G. MA408 | Discrete Mathematics and Graph Theory Assessed Coursework | Page 3 Suppose that G has 2k2n vertices (we assume V(G) is disjoint from [2k2n]), and c is an equitable

(2k2)-colouring of G(2). Consider the following algorithm, which for input (G, c, p), where p 2 [0, 1] may depend on n, returns a graph H on 2k2n vertices and either an embedding f of G into H or 'Fail'.

Algorithm 1: Embed(G, c, p) Let V(H) = [2k2n] ;

Let f1 : c􀀀1(1) ! V(H) be an arbitrary injective map with image f1, . . . , ng ; For each unordered pair x, y in f1, . . . , ng, independently, add xy to H with probability p ;

foreach i = 2, . . . , 2k2 do For each unordered pair x, y with x 2 [in] and y 2 f(i 􀀀 1)n + 1, . . . , ing, independently, add xy to H with probability p ; if fi􀀀1 6= 'Fail' then Let V(Fi) = c􀀀1(i) [ f(i 􀀀 1)n + 1, . . . , ing ; foreach u 2 c􀀀1(i) and x 2 f(i 􀀀 1)n + 1, . . . , ing do

If fi􀀀1(v)x is an edge of H for each neighbour v of u with c(v) < i, add ux to Fi ; end if Fi has a perfect matching then

Let M be a perfect matching in Fi ; Define fi : c􀀀1(f1, . . . , ig) ! V(H) by fi(u) = fi􀀀1(u) if c(u) < i and fi(u) = x if c(u) = i and ux 2 M ;

end else