EN|RU
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:4, 514-520

Volume 24, No 4, 2017, P. 34–46

UDC 519.174
M. O. Golovachev and A. V. Pyatkin
On ($1, l$)-coloring of incidentors of multigraphs

Abstract:
It is proved that if $l$ is at least $\Delta/2 - 1$ then (1, $l$)-chromatic number of an arbitrary multigraph of maximum degree $\Delta$ is at most $\Delta + 1$. Moreover, it is proved that the incidentors of every directed prism can be colored in four colors so that every two adjacent incidentors are colored distinctly and the difference between the colors of the final and initial incidentors of each arc is 1.
Illustr. 1, bibliogr. 10.

Keywords: incidentor coloring, (1, $l$)-coloring, prism.

DOI: 10.17377/daio.2017.24.572

Mikhail O. Golovachev 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: mik-golovachev2@mail.ru, artem@math.nsc.ru

Revised 10 April 2017

# References

[1] 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].

[2] V. G. Vizing, On linear factors of multigraphs, Diskretn. Anal. Issled. Oper., Ser. 1, 10, No. 4, 3–7, 2003 [Russian].

[3] 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].

[4] A. V. Pyatkin, Some optimization problems of scheduling the transmission 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).

[5] 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].

[6] 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].

[7] R. Diestel, Graph Theory, Springer, Heidelberg, 2017 (Grad. Texts Math., Vol. 173).

[8] L. S. Mel’nikov and V. G. Vizing, The edge chromatic number of a directed/mixed multigraph, J. Graph Theory, 31, No. 4, 267–273, 1999.

[9] J. Petersen, The theory of regular graphs, Acta Math., 15, 193–220, 1891 [German].

[10] D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, 2001.
© Sobolev Institute of Mathematics, 2015