TY - JOUR

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

AU - Glebov, A. N.

AU - Pavlov, I. A.

AU - Khadaev, K. A.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - graph

KW - multigraph

KW - edge

KW - colouring

KW - list colouring

KW - forbiddance

KW - LIST-CHROMATIC INDEX

U2 - 10.33048/semi.2020.17.042

DO - 10.33048/semi.2020.17.042

M3 - статья

VL - 17

SP - 637

EP - 646

JO - Сибирские электронные математические известия

JF - Сибирские электронные математические известия

SN - 1813-3304

ER -