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 c1(i) which has no neighbours in c1(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
c1(i)
=
c1(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
c1(1)
c1(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
c1(n)
>
c1(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 : c1(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 fi1 6= ‘Fail' then
Let V(Fi) = c1(i) [ f(i 1)n + 1, . . . , ing ;
foreach u 2 c1(i) and x 2 f(i 1)n + 1, . . . , ing do
If fi1(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 : c1(f1, . . . , ig) ! V(H) by fi(u) = fi1(u) if c(u) < i and
fi(u) = x if c(u) = i and ux 2 M ;
end
else