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

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

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

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.
Переведенное названиеVertex colouring of multigraphs with forbiddances on edges
Язык оригиналарусский
Страницы (с-по)637-646
Число страниц10
ЖурналСибирские электронные математические известия
Том17
DOI
СостояниеОпубликовано - 2020

Ключевые слова

  • graph
  • multigraph
  • edge
  • colouring
  • list colouring
  • forbiddance
  • LIST-CHROMATIC INDEX

Предметные области OECD FOS+WOS

  • 1.01 МАТЕМАТИКА

Fingerprint

Подробные сведения о темах исследования «Раскраски вершин мультиграфов с запретами на ребрах». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать