Single-conflict colouring

Abstract

Given a multigraph, suppose that each vertex is given a local assignment of $k$ 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 $k$ 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 $g$ is $O\left(g^{1∕4}\log g\right)$ as $g\to \infty$ . This is sharp up to the logarithmic factor.

Keywords: DP‐colouring; adaptable choosability; graphs on surfaces; list colouring; single‐conflict chromatic number.