Edge-colourings of graphs

Chetwynd, Amanda Gillian (1984). Edge-colourings of graphs. PhD thesis The Open University.

DOI: https://doi.org/10.21954/ou.ro.0000f7e7

Abstract

All the results in this thesis are concerned with the classification of graphs by their chromatic class.

We first extend earlier results of Fiorini and others to give a complete list of critical graphs of order at most ten. We give conditions for extending the edge-colouring of a nearly complete subgraph to the whole graph and use this result to prove a special case of Vizing's conjecture. We also use other methods to solve further cases of this conjecture.

A major part of the thesis classifies those graphs with at most 4 vertices of maximum degree and this work is generalised to graphs with r vertices of maximum degree. We also completely classify all regular graphs G with degree at least 6/7|V(G)|.

Finally we give some examples of even order critical graphs and introduce the concept of a supersnark.