EDGE-COLOURING OF GRAPHS AND EMBEDDINGS OF PARTIAL LATIN SQUARES

Abstract

Let G be a graph with edge sete E(G) and maximum degree ?(G). An edge colouring ? of G is a mapping from E(G) to a set C such that no two adjacent edges have the same image. A great breakthrough in this field occurred in 1964 when V.G. Vizing proved that x’(G), the minimum number of colours needed to colour all the edges of G, either ?(G) or ?(G) +1. Since then, edge colourings of graphs have attracted more and more people’s attention. Nowadays, it is widely applied to scheduling, timetable designing, and to other mathematics fields like latin squares, combinatorial designs and matroid theory. A latin square side of n is an nxn matrix on n symbols such that no symbol occurs more than once in any row or in any column. It is well-known that there exists a 1-1 correspondence between latin squares of side n and n-edge colourings of balanced complete bipartite graph Kn,n. THe three problems studied in this thesis are: (1) what kind of multicoloured graphs or order n, i.e. graphs whose edges are coloured with distinct colours, can be embedded in a ?’(Kn)-edge coloured Kn? (2) what kind of partial latin squares can be embedded in latin squares of the same side? (3) can we suitably edge colour the complete graph K2n such that it can be partitioned into multicoloured spanning trees?