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

Translated title of the contribution: Vertex colouring of multigraphs with forbiddances on edges

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

Research output: Contribution to journalArticlepeer-review


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 >= 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.
Translated title of the contributionVertex colouring of multigraphs with forbiddances on edges
Original languageRussian
Pages (from-to)637-646
Number of pages10
JournalСибирские электронные математические известия
Publication statusPublished - 2020


Dive into the research topics of 'Vertex colouring of multigraphs with forbiddances on edges'. Together they form a unique fingerprint.

Cite this