On fractional colourings of graphs and related problems

Abstract

One of the most well known and extensively studied areas within graph theory is without any doubt “colouring”. The first problems in graph colourings that have received great attention involve colouring the vertices or the edges of a graph. Various extensions to these two fundamental problems have been introduced throughout the years, such as total colourings, local colourings and fractional colourings, among others. In this thesis we shall focus on fractional colourings of graphs and some problems that are related to these colourings. Let G be a simple graph (with no loops or multiple edges) having vertex set V(G) and edge set E(G). A proper vertex-colouring of G is an assignment of colours to the vertices of G such that adjacent vertices receive different colours. If G can be properly coloured using k colours, we say that G is k-colourable. The chromatic number c(G) of G is the least number of colours required such that G has a proper colouring. Analogously, an edge-colouring of G is a function that assigns a colour to each edge of G. If edges having a common end-vertex are assigned distinct colours, then the edge-colouring is called a proper edge-colouring. Moreover, if a proper edge-colouring uses k colours we say that G is k-edge-colourable. The minimum positive integer k such that G is k-edge-colourable is the chromatic index of G, denoted by c0(G). A detailed historical background on this area and fundamental results on vertex- and edge-colourings are given in [6]. A related problem investigates the fractional colouring of a graph G. Let I(G) denote the set of all independent sets of G, where an independent set is a set of pairwise non-adjacent vertices. Let I(G;v) denote all the independent sets of G that contain v, for some v 2 V(G). A fractional colouring of a graph G is a function f that assigns a non-negative real value to all possible colour-classes of G containing any vertex v of G (that is, the independent sets I(G;v)), such that the sum of these values is at least one for each vertex. In this dissertation we survey the existing literature on fractional parameters of graphs. The aim of this research is to present and analyse the main results on fractional covers and fractional cliques [4, 14], and on fractional colourings and the fractional chromatic number [14, 24]. We then apply some of these notions, techniques and conclusions to derive results for various families of graphs. Finally, we study how the different fractional parameters are interrelated and investigate their application to a relaxation of the EFL conjecture and to other related problems.