Vertex colourings of multigraphs with forbiddances on edges

A. N. Glebov ; I. A. Pavlov ; K. A. Khadaev

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 637-646

Résumé

We define and study a new class of vertex colourings of multigraphs, where some pairs of colours are forbidden on the edges of a multigraph. We say that a multigraph $G$ is (properly) $(m,r)$-colourable if for any given sets of $r$ forbidden pairs of colours on the edges of $G$ where exists a (proper) vertex $m$-colouring of $G$ that respects all forbidden pairs. We determine all (properly) $(m,r)$-colourable stars, all $(2,r)$-colourable multigraphs for each $r\ge 1$ and all $(m,r)$-colourable multighraphs, where $r$ is large enough (close to $m^2$). We also introduce a list version of $(m,r)$-colourability and establish (for the case of improper colourings) that the list $(m,r)$-colourability of a multigraph is equivalent to its $(m,r)$-colourability.

Détail

Keywords: graph, multigraph, edge, colouring, list colouring, forbiddance.