A note on choosability with defect 1 of graphs on surfaces
share
This note proves that every graph of Euler genus μ is 2 + √(3μ + 3) --choosable with defect 1 (that is, clustering 2). Thus, allowing defect as small as 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.
READ FULL TEXT