Defect-1 Choosability of Graphs on Surfaces

Abstract

The classical (proper) graph colouring problem asks for a colouring of the vertices of a graph with the minimum number of colours such that no two vertices with the same colour are adjacent. Equivalently the colouring is required to be such that the graph induced by the vertices coloured the same colour has the maximum degree equal to zero. The graph parameter associated with the minimum possible number of colours of a graph is called chromatic number of that graph. One generalization of this classical problem is to relax the requirement that the maximum degree of the graph induced by the vertices coloured the same colour be zero, and instead allow it to be some integer d. For d = 0, we are back at the classical proper colouring. For other values of d we say that the colouring has defect d. Another generalization of the classical graph colouring, is list colouring and its associated parameters: choosability and choice number. The main result of this thesis is to show that every graph G of Euler genus μ is ⌈2 + √(3μ + 3)⌉–choosable with defect 1 (equivalently, with clustering 2). Thus allowing any defect, even 1, reduces the choice number of surface embeddable graphs below the chromatic number of the surface. For example, the chromatic number of the family of toroidal graphs is known to be 7. The bound above implies that toroidal graphs are 5-choosable with defect 1. This strengthens the result of Cowen, Goddard and Jesurum (1997) who showed that toroidal graphs are 5-colourable with defect 1. In a graph embedded in a surface, two faces that share an edge are called adjacent. We improve the above bound for graphs that have embeddings without adjacent triangles. In particular, we show that every non-planar graph G that can be embedded in a surface of Euler genus μ without adjacent triangles, is ⌈(5+ √(24μ + 1)) /3⌉–choosable with defect 1. This result generalizes the result of Xu and Zhang (2007) to all the surfaces. They proved that toroidal graphs that have embeddings on the torus without two adjacent triangles are 4-choosable with defect 1.