Volume 22, No 2, 2015, P. 63–72

UDC 519.174
A. V. Pyatkin
On interval (1, 1)-coloring of incidentors of interval colorable graphs

Abstract:
A graph is interval colorable if it has a proper edge coloring such that for every vertex the colors used for coloring edges adjacent to it form an interval. A subdivision of a graph is a graph obtained by substituting a path of length two for each edge. P. Petrosyan and H. Khachatrian posed a conjecture that the subdivision of each interval colorable graph is interval colorable. In this paper, we prove this conjecture.
Bibliogr. 19.

Keywords: interval coloring, incidentor, graph subdivision.

DOI: 10.17377/daio.2015.22.454

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: artem@math.nsc.ru

Received 2 June 2014
Revised 24 November 2014

References

[1] A. S. Asratian and R. R. Kamalian, Interval colorings of edges of a multigraph, Prikl. Mat., Erevan, 5, 25–34, 1987.

[2] V. G. Vizing, Interval coloring of the incidentors of a directed multigraph, Diskretn. Anal. Issled. Oper., Ser. 1, 8, No. 2, 40–51, 2001.

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

[4] V. G. Vizing, Interval coloring of the incidentors of an undirected multigraph, Diskretn. Anal. Issled. Oper., Ser. 1, 10, No. 1, 14–40, 2003.

[5] V. G. Vizing, Strict coloring of incidentors of undirected multigraphs, Diskretn. Anal. Issled. Oper., Ser. 1, 12, No. 3, 48–53, 2005.

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

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

[8] V. G. Vizing and A. V. Pyatkin, Incidentor coloring of multigraphs, in R. I. Tyshkevich, ed., Topics in Graph Theory, pp. 197–209, Urbana–Champaign, USA, 2013. Available at http://www.math.uiuc.edu/˜kostochk/.
Accessed Mar. 3, 2015.

[9] 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. Translated in A. D. Korshunov, ed., Operations Research and Discrete Analysis, pp. 227–232, Kluwer Acad. Publ., Netherlands, 1997 (Math. Its Appl., Vol. 391).

[10] A. V. Pyatkin, (k, l)-Coloring of incidentors of cubic multigraphs, Diskretn. Anal. Issled. Oper., Ser. 1, 9, No. 1, 49–53, 2002.

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

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

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

[14] S. V. Sevastyanov, On interval colorability of the edges in a bipartite graph, in Metody diskretnogo analiza v reshenii ekstremal’nykh zadach (Methods of Discrete Analysis in Solving Extremal Problems), Vol. 50, pp. 61–72, Inst. Mat. SO AN SSSR, Novosibirsk, 1990.

[15] A. S. Asratian and R. R. Kamalian, Investigation of interval edge-colorings of graphs, J. Comb. Theory, Ser. B, 62, No. 1, 34–43, 1994.

[16] H. M. Hansen, Scheduling with minimum waiting periods, Master Thesis, Odense Univ., Odense, Denmark, 1992.

[17] D. Hanson, C. O. M. Loten, and B. Toft, On interval colourings of bi-regular bipartite graphs, Ars Comb., 50, 23–32, 1998.

[18] P. A. Petrosyan and H. H. Khachatrian, Interval non-edge-colorable bipartite graphs and multigraphs, J. Graph Theory, 76, No. 3, 200–216, 2014.

[19] W. Lipsky, Jr., One more polynomial complete consecutive retrieval prob- lem, Inf. Process. Lett., 6, No. 3, 91–93, 1977.