Fractional edge and total colouring
W. Sean Kennedy · eScholarship@McGill (McGill) · 2012
Many problems which seek to schedule, sequence, or time-table a set of events subject to given constraints can be modelled as graph colouring problems. In this thesis, we study the edge and total colouring problems which, like all NP problems, can be formulated as integer programs and subjected to a two-pronged attack: we first solve the fractional relaxation and then use this solution to solve or obtain an approximation of the solution of the integer program. We focus on the complexity of solving the fractional relaxations of the integer programs for the edge and total colouring problems. For each ε > 0, we give a linear time algorithm which determines the fractional chromatic index of a graph $G$ with maximum degree at least ε|G|. For graphs with large maximum degree, this improves on Padberg and Rao's polynomial time algorithm to determine the fractional chromatic index for general graphs. Both algorithms rely on a theorem of Edmonds showing that the fractional chromatic index of a graph is determined by its maximum degree and overfull subgraphs. Our algorithm exploits the fact that overfull subgraphs are related to small cuts in a graph and have simple intersection patterns when the maximum degree is large. The complexity of determining the fractional total colouring number is currently unresolved. We focus on graphs with large maximum degree, applying the very successful techniques for fractional edge colouring to fractional total colouring. We characterize graphs with maximum degree Δ whose fractional total colouring number is Δ + 2, sharpening a result of Kilakos and Reed who showed it is between Δ + 1 and Δ+2. We show graphs whose fractional total colouring number is less than Δ + 2 have a special fractional vertex colouring which extends to a fractional total colouring using less than Δ + 2 colours. We extend these ideas by giving necessary conditions a fractional vertex ß-colouring must satisfy to be extendable to a fractional total ß-colouring. We conjecture these conditions are sufficient when G satisfies Δ > ½|G|. We verify a special case of this conjecture by giving a polynomial time algorithm which constructs an optimal fractional total colouring of a graph G with maximum degree at least ¾|G| and containing no overfull subgraphs.