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

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

REFERENCES

1.   Vasil’eva E.I., Pyatkin A.V. On list incidentor (k,l)-coloring. J. Appl. Industrial Math., 2017, vol. 11, no. 1, pp. 125–129. doi: 10.1134/S1990478917010148 

2.   Vizing V.G. Coloring the graph vertices with some prescribed colors. In: Methods of Discrete Analysis in the Theory of Codes and Schemes, vol. 29 (Inst. Math. SO AN SSSR, Novosibirsk, 1976), pp. 3–10 (in Russian).

3.   Vizing V.G. Incidentor coloring of multigraphs in prescribed colors. Diskretn. Anal. Issled. Oper. Ser. 1, 2000, vol. 7, no. 1, pp. 32–39 (in Russian).

4.   Vizing V.G., Melnikov L.S., Pyatkin A.V. On (k,l)-coloring of incidentors. Diskretn. Anal. Issled. Oper. Ser. 1, 2000, vol. 7, no. 4, pp. 29–37 (in Russian).

5.   Pyatkin A.V. Some optimization problems of scheduling the transmission of messages in a local communication network. In: A.D. Korshunov (ed.), Operations Research and Discrete Analysis. Netherlands: Kluwer Acad. Publ., 1997, pp. 227–232. doi: 10.1007/978-94-011-5678-3_17 

6.   Bollobas B., Harris A.J. List-colorings of graphs. Graphs Combin., 1985, vol. 1, no. 1, pp. 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, pp. 184–204. doi: 10.1006/jctb.1997.1780 

8.   Diestel R. Graph theory. Graduate Texts in Math., vol. 173, 5th ed. Heidelberg: Springer-Verlag, 2016, 448 p. ISBN: 978-3-662-53621-6 .

9.   Erdos P., Rubin A.L., Taylor H. Choosability in graphs. In: Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Vol 26 of Congressus Numerantium, Arcata, California, 1979, pp. 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, pp. 503–516. doi: 10.1002/jgt.3190160206 

11.   Hall P. On representatives of subsets. J. London Math. Soc., 1935, vol. 10, no. 1, pp. 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. ISBN: 0-13-014400-2 .

13.   Woodall D.R. List colourings of graphs. In: J. W. P. Hirschfeld (ed.) Surveys in combinatorics, 2001, London Math. Soc. Lecture Note Ser., vol. 288, Cambridge: Cambridge Univ. Press, 2001, pp. 269–301. ISBN: 0-521-00270-2 ,

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.