Standard

Раскраски вершин мультиграфов с запретами на ребрах. / Glebov, A. N.; Pavlov, I. A.; Khadaev, K. A.

в: Сибирские электронные математические известия, Том 17, 2020, стр. 637-646.

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

Harvard

Glebov, AN, Pavlov, IA & Khadaev, KA 2020, 'Раскраски вершин мультиграфов с запретами на ребрах', Сибирские электронные математические известия, Том. 17, стр. 637-646. https://doi.org/10.33048/semi.2020.17.042

APA

Glebov, A. N., Pavlov, I. A., & Khadaev, K. A. (2020). Раскраски вершин мультиграфов с запретами на ребрах. Сибирские электронные математические известия, 17, 637-646. https://doi.org/10.33048/semi.2020.17.042

Vancouver

Glebov AN, Pavlov IA, Khadaev KA. Раскраски вершин мультиграфов с запретами на ребрах. Сибирские электронные математические известия. 2020;17:637-646. doi: 10.33048/semi.2020.17.042

Author

Glebov, A. N. ; Pavlov, I. A. ; Khadaev, K. A. / Раскраски вершин мультиграфов с запретами на ребрах. в: Сибирские электронные математические известия. 2020 ; Том 17. стр. 637-646.

BibTeX

@article{0d77d3f6216745dbbdb4237df6d4752c,
title = "Раскраски вершин мультиграфов с запретами на ребрах",
abstract = "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.",
keywords = "graph, multigraph, edge, colouring, list colouring, forbiddance, LIST-CHROMATIC INDEX",
author = "Glebov, {A. N.} and Pavlov, {I. A.} and Khadaev, {K. A.}",
year = "2020",
doi = "10.33048/semi.2020.17.042",
language = "русский",
volume = "17",
pages = "637--646",
journal = "Сибирские электронные математические известия",
issn = "1813-3304",
publisher = "Sobolev Institute of Mathematics",

}

RIS

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 -

ID: 26075932