|
О предписанной $(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)$-раскраска.
Поступила в редакцию: 10.01.2019
Образец цитирования:
А. В. Пяткин, “О предписанной $(k,l)$-раскраске инциденторов мультиграфов четной степени при некоторых значениях $k$ и $l$”, Тр. ИММ УрО РАН, 25, № 2, 2019, 177–184
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1634 https://www.mathnet.ru/rus/timm/v25/i2/p177
|
Статистика просмотров: |
Страница аннотации: | 144 | PDF полного текста: | 28 | Список литературы: | 21 | Первая страница: | 2 |
|