Дискретная математика и математическая кибернетика
Раскраски вершин мультиграфов с запретами на ребрах
А. Н. Глебовa,
И. А. Павловb,
К. А. Хадаевc a Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
b Novosibirsk State University, 2, Pirogova str., Novosibirsk, 630090, Russia
c Higher School of Economics, 20, Myasnitskaya str., Moscow, 101000, Russia
Аннотация:
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.
Ключевые слова:
graph, multigraph, edge, colouring, list colouring, forbiddance.
УДК:
519.172.2,
519.174
MSC: 05C10,
05C15,
05C70 Поступила 3 ноября 2018 г., опубликована
24 апреля 2020 г.
DOI:
10.33048/semi.2020.17.042