RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2020, том 17, страницы 637–646 (Mi semr1237)

Дискретная математика и математическая кибернетика

Раскраски вершин мультиграфов с запретами на ребрах

А. Н. Глебов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



Реферативные базы данных:


© МИАН, 2024