Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:1, 125-129
Volume 24, No 1, 2017, P. 21-30
UDC 519.8
E. I. Vasilyeva and A. V. Pyatkin
On list incidentor $(k, l)$-colorings
Abstract:
A proper incidentor coloring is called a $(k, l)$-coloring if the difference between the colors of the final and initial incidentors ranges between $k$ and $l$. In the list variant, the extra restriction is added: The color of each incidentor must belong to the set of admissible colors of the arc. In order to make this restriction reasonable we assume that the set of admissible colors for each arc is an integer interval. The minimum length of the interval that guarantees the existence of a list incidentor $(k, l)$-coloring is called a list incidentor $(k, l)$-chromatic number. Some bounds for the list incidentor $(k, l)$-chromatic number are proved for multigraphs of degree 2 and 4.
Bibliogr. 13.
Keywords: list coloring, incidentor, $(k, l)$-coloring.
DOI: 10.17377/daio.2017.24.542
Ekaterina I. Vasilyeva 2
Artem V. Pyatkin 1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: ekaterinavasilyeva93@gmail.com, artem@math.nsc.ru
Received 24 May 2016
Revised 6 June 2016
References
[1] V. G. Vizing, Incidentor coloring of multigraphs in prescribed colors, Diskretn. Anal. Issled. Oper., Ser. 1, 7, No. 1, 32–39, 2000 [Russian].[2] V. G. Vizing, A bipartite interpretation of a directed multigraph in problems of the coloring of incidentors, Diskretn. Anal. Issled. Oper., Ser. 1, 9, No. 1, 27–41, 2002 [Russian].
[3] V. G. Vizing, Strict coloring of incidentors in undirected multigraphs, Diskretn. Anal. Issled. Oper., Ser. 1, 12, No. 3, 48–53, 2005 [Russian].
[4] V. G. Vizing, On the $(p, q)$-coloring of incidentors of an undirected multigraph, Diskretn. Anal. Issled. Oper., Ser. 1, 12, No. 4, 23–39, 2005 [Russian].
[5] V. G. Vizing, L. S. Mel’nikov, and A. V. Pyatkin, On the $(k, l)$-coloring of incidentors, Diskretn. Anal. Issled. Oper., Ser. 1, 7, No. 4, 29–37, 2000 [Russian].
[6] V. G. Vizing and A. V. Pyatkin, Incidentor coloring of multigraphs, in R. I. Tyshkevich, ed., Topics in Graph Theory, pp. 197–209, Urbana, USA, 2013 [Russian]. Available at http://www.math.uiuc.edu/˜kostochk/. Accessed Mar. 3, 2015.
[7] A. V. Pyatkin, Some problems for optimizing the routing of messages in a local communication network, Diskretn. Anal. Issled. Oper., 2, No. 4, 74–79, 1995 [Russian]. Translated in A. D. Korshunov, ed., Operations Research and Discrete Analysis, pp. 227–232, Kluwer Acad. Publ., Dordrecht, 1997 (Math. Appl., Vol. 391).
[8] A. V. Pyatkin, $(k, l)$-Coloring of incidentors of cubic multigraphs, Diskretn. Anal. Issled. Oper., Ser. 1, 9, No. 1, 49–53, 2002 [Russian].
[9] A. V. Pyatkin, Some upper bounds for the incidentor $(k, l)$-chromatic number, Diskretn. Anal. Issled. Oper., Ser. 1, 10, No. 2, 66–78, 2003 [Russian].
[10] A. V. Pyatkin, Upper and lower bounds for the incidentor $(k, l)$-chromatic number, Diskretn. Anal. Issled. Oper., Ser. 1, 11, No. 1, 93–102, 2004 [Russian].
[11] A. V. Pyatkin, On (1, 1)-coloring of incidentors of multigraphs of degree 4, Diskretn. Anal. Issled. Oper., Ser. 1, 11, No. 3, 59–62, 2004 [Russian].
[12] A. V. Pyatkin, On list incidentor coloring of a multigraph of degree 3, Diskretn. Anal. Issled. Oper., Ser. 1, 14, No. 3, 80–89, 2007 [Russian]. Translated in J. Appl. Ind. Math., 2, No. 4, 560-565, 2008.
[13] O. V. Borodin, A. V. Kostochka, and D. R. Woodall, List edge and list total colorings of multigraphs, J. Comb. Theory, Ser. B, 71, No. 2, 184–204, 1997.
