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

УДК 519.174

MSC: 05C15

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

Полный текст статьи (Full text)

Работа выполнена при поддержке программы фундаментальных научных исследований СО РАН № I.5.1 (проект 0314-2019-0014) и РФФИ (проект 17-01-00170).

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

$\bullet \ l\ge k+\Delta/2$;

$\bullet  \ l< k+\Delta/2, k \mbox{ или } l$ нечетно;

$\bullet \ l< k+\Delta/2, k=0 \mbox{ или } l-k=2$;

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

СПИСОК ЛИТЕРАТУРЫ

1.   Васильева Е.И., Пяткин А.В. О предписанной (k,l)-раскраске инциденторов // Дискрет. анализ и исслед. операций. 2017. Том 24, № 1. С. 21–30. doi: 10.17377/daio.2017.24.542 

2.   Визинг В. Г. Раскраска вершин графа в предписанные цвета / / Методы дискретного анализа в теории кодов и схем: cб. науч. тр. / Ин-т математики СО АН СССР. Новосибирск, 1976. Вып. 29. С. –10.

3.   Визинг В. Г. Раскраска инциденторов мультиграфа в предписанные цвета // Дискрет. анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 1. С. 32–39.

4.   Визинг В. Г., Мельников Л. С., Пяткин А. В. О (k,l)-раскраске инциденторов // Дискрет. анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 4. С. 29–37.

5.   Пяткин А. В. Hекотоpые задачи оптимизации pасписания пеpедачи сообщений в локальной сети связи // Дискрет. анализ и исслед. опеpаций. 1995. Т. 2. № 4. С. 74–79.

6.   Bollobas B., Harris A.J. List-colorings of graphs // Graphs Combin. 1985. Vol. 1, no. 1. P. 115–127. doi: 10.1007/BF02582936 

7.   Borodin O. V., Kostocka A. V., Woodall D. R. List edge and list total colorings of multigraphs // J. Combin. Theory. Ser. B. 1997. Vol. 71, no. 2. P. 184–204. doi: 10.1006/jctb.1997.1780 

8.   Diestel R. Graph theory. 5th ed. Heidelberg: Springer-Verlag, 2016. 448 p. (Graduate Texts in Math.; vol. 173).

9.   Erdos P., Rubin A.L., Taylor H. Choosability in graphs // Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing. Vol. 16 of Congressus Numerantium. Arcata, California, 1979. P. 125–157.

10.   H$\ddot{\mathrm{a}}$ggkvist R., Chetwynd A.G. Some upper bounds on the total and list chromatic numbers of multigraphs // J. Graph Theory. 1992. Vol. 16, no. 2. P. 503–516. doi: 10.1002/jgt.3190160206 

11.   Hall P. On representatives of subsets // J. London Math. Soc. 1935. Vol. 10, no. 1. P. 26–30. doi:10.1112/jlms/s1-10.37.26 

12.   West D.B. Introduction to graph theory. New Jersey: Prentice Hall, 2001. 588 p.

13.   Woodall D. R. List colourings of graphs // Surveys in combinatorics / ed. J. W. P. Hirschfeld Cambridge: Cambridge Univ. Press, 2001. P. 269–301. (London Math. Soc. Lecture Note Series; vol. 288)

Поступила 10.01.2019

После доработки 16.05.2019

Принята к публикации 20.05.2019

Пяткин Артем Валерьевич
д-р физ.-мат. наук, доцент, профессор РАН
главный науч. сотрудник
Институт математики им. С.Л.Соболева СО РАН;
профессор
Новосибирский государственный университет
г. Новосибирск
e-mail: artem@math.nsc.ru

Ссылка на статью: А.В. Пяткин. О предписанной (k,l)-раскраске инциденторов мультиграфов четной степени при некоторых значениях k и l // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 2. С. 177-184.

English

A.V. Pyatkin. On a list (k,l)-coloring of incidentors in multigraphs of even degree for some values of k and l

The problem of a list $(k,l)$-coloring of incidentors of a directed multigraph without loops is studied in the case where the lists of admissible colors for incidentors of each arc are integer intervals. According to a known conjecture, if the lengths of these interval are at least $2\Delta+2k-l-1$ for every arc, where $\Delta$ is the maximum degree of the multigraph, then there exists a list $(k,l)$-coloring of incidentors. We prove this conjecture for multigraphs of even maximum degree $\Delta$ with the following parameters:

$\bullet \ l\ge k+\Delta/2$;

$\bullet \ l< k+\Delta/2$ and $k$ or $l$ is odd;

$\bullet \ l< k+\Delta/2$ and $k=0$ or $l-k=2$.

Keywords: list coloring, incidentors, (k,l)-coloring

Received January 10, 2019

Revised May 16, 2019

Accepted May 20, 2019

Funding Agency: This work was supported by Program I.5.1 for Fundamental Research of the Siberian Branch of the Russian Academy of Sciences (project no. 0314-2019-0014) and by the Russian Foundation for Basic Research (project no. 17-01-00170).

Artem Valer’evich Pyatkin, Dr. Phys.-Math. Sci., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630090 Russia, e-mail: artem@math.nsc.ru

Cite this article as: A.V.Pyatkin. On a list (k,l)-coloring of incidentors in multigraphs of even degree for some values of k and l, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 2, pp. 177–184.

[References -> on the "English" button bottom right]