pith. sign in

arxiv: 1806.06149 · v1 · pith:5QACUTEFnew · submitted 2018-06-15 · 💻 cs.DM

A note on choosability with defect 1 of graphs on surfaces

classification 💻 cs.DM
keywords defectgraphsnumbertoroidalchoosablechromaticnotesurface
0
0 comments X
read the original abstract

This note proves that every graph of Euler genus $\mu$ is $\lceil 2 + \sqrt{3\mu + 3}\,\rceil$--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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.