Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
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
Received 22 March 2017
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.
