Paper 1, Section II, 16G

Graph Theory
Part II, 2016

(a) Show that if GG is a planar graph then χ(G)5\chi(G) \leqslant 5. [You may assume Euler's formula, provided that you state it precisely.]

(b) (i) Prove that if GG is a triangle-free planar graph then χ(G)4\chi(G) \leqslant 4.

(ii) Prove that if GG is a planar graph of girth at least 6 then χ(G)3\chi(G) \leqslant 3.

(iii) Does there exist a constant gg such that, if GG is a planar graph of girth at least gg, then χ(G)2?\chi(G) \leqslant 2 ? Justify your answer.