RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Института математики и механики УрО РАН // Архив

Тр. ИММ УрО РАН, 2019, том 25, номер 2, страницы 177–184 (Mi timm1634)

О предписанной $(k,l)$-раскраске инциденторов мультиграфов четной степени при некоторых значениях $k$ и $l$

А. В. Пяткинab

a Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск
b Новосибирский национальный исследовательский государственный университет

Аннотация: Исследуется задача предписанной $(k,l)$-раскраски инциденторов ориентированного мультиграфа без петель, в которой множество допустимых цветов инциденторов каждой дуги образует целочисленный интервал. Известна гипотеза, что если длина этого интервала не меньше $2\Delta+2k-l-1$ для каждой дуги, где $\Delta$ - это максимальная степень мультиграфа, то инциденторы мультиграфа допускают $(k,l)$-раскраску с таким предписанием. В настоящей работе приводится доказательство этой гипотезы для мультиграфов четной максимальной степени $\Delta$ при следующих параметрах:
$\bullet \ l\ge k+\Delta/2$;
$\bullet  \ l< k+\Delta/2, k$ или $l$ нечетно;
$\bullet \ l< k+\Delta/2, k=0 $ или $l-k=2$;

Ключевые слова: предписанная раскраска, инциденторы, $(k,l)$-раскраска.

УДК: 519.174

MSC: 05C15

Поступила в редакцию: 10.01.2019

DOI: 10.21538/0134-4889-2019-25-2-177-184



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


© МИАН, 2024