Given a multigraph, suppose that each vertex is given a local assignment of colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least for which this is always possible given any set of local assignments we call the single-conflict chromatic number of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that single-conflict chromatic number of simple graphs embeddable on a surface of Euler genus is as . This is sharp up to the logarithmic factor.
Keywords: DP‐colouring; adaptable choosability; graphs on surfaces; list colouring; single‐conflict chromatic number.
© 2020 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.