Geodesic
On interval $(1,1)$-coloring of incidentors of interval colorable graphs
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 2, pp. 63-72.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2015_22_2_a4,
     author = {A. V. Pyatkin},
     title = {On interval $(1,1)$-coloring of incidentors of interval colorable graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {63--72},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_2_a4/}
}
TY  - JOUR
AU  - A. V. Pyatkin
TI  - On interval $(1,1)$-coloring of incidentors of interval colorable graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 63
EP  - 72
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_2_a4/
LA  - ru
ID  - DA_2015_22_2_a4
ER  - 
%0 Journal Article
%A A. V. Pyatkin
%T On interval $(1,1)$-coloring of incidentors of interval colorable graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 63-72
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_2_a4/
%G ru
%F DA_2015_22_2_a4
A. V. Pyatkin. On interval $(1,1)$-coloring of incidentors of interval colorable graphs. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 2, pp. 63-72. http://geodesic.mathdoc.fr/item/DA_2015_22_2_a4/

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

[2] V. G. Vizing, “Interval coloring of the incidentors of a directed multigraph”, Diskretn. Anal. Issled. Oper., Ser. 1, 8:2 (2001), 40–51 | MR | Zbl

[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:1 (2002), 27–41 | MR

[4] V. G. Vizing, “Interval coloring of the incidentors of an undirected multigraph”, Diskretn. Anal. Issled. Oper., Ser. 1, 10:1 (2003), 14–40 | MR | Zbl

[5] V. G. Vizing, “Strict coloring of incidentors of undirected multigraphs”, Diskretn. Anal. Issled. Oper., Ser. 1, 12:3 (2005), 48–53 | MR | Zbl

[6] V. G. Vizing, “On the $(p,q)$-coloring of incidentors of an undirected multigraph”, Diskretn. Anal. Issled. Oper., Ser. 1, 12:4 (2005), 23–39 | MR | Zbl

[7] V. G. Vizing, L. S. Mel'nikov, A. V. Pyatkin, “On the $(k,l)$-coloring of incidentors”, Diskretn. Anal. Issled. Oper., Ser. 1, 7:4 (2000), 29–37 | MR | Zbl

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

[9] Pyatkin A. V., “Some problems for optimizing the routing of messages in a local communication network”, Operations Research and Discrete Analysis, Math. Its Appl., 391, ed. A. D. Korshunov, Kluwer Acad. Publ., Netherlands, 1997, 227–232 | MR | Zbl

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

[11] A. V. Pyatkin, “Some upper bounds for the incidentor $(k,l)$-chromatic number”, Diskretn. Anal. Issled. Oper., Ser. 1, 10:2 (2003), 66–78 | MR | Zbl

[12] A. V. Pyatkin, “Upper and lower bounds for the incidentor $(k,l)$-chromatic number”, Diskretn. Anal. Issled. Oper., Ser. 1, 11:1 (2004), 93–102 | MR | Zbl

[13] A. V. Pyatkin, “On $(1,1)$-coloring of incidentors of multigraphs of degree 4”, Diskretn. Anal. Issled. Oper., Ser. 1, 11:3 (2004), 59–62 | MR | Zbl

[14] S. V. Sevastyanov, “On interval colorability of the edges in a bipartite graph”, Methods of Discrete Analysis in Solving Extremal Problems, 50, Inst. Mat. SO AN SSSR, Novosibirsk, 1990, 61–72 | MR

[15] Asratian A. S., Kamalian R. R., “Investigation of interval edge-colorings of graphs”, J. Comb. Theory. Ser. B, 62:1 (1964), 34–43 | DOI | MR

[16] Hansen H. M., Scheduling with minimum waiting periods, Thes. $\dots$ magister sci., Odense Univ., Odense, Denmark, 1992

[17] Hanson D., Loten C. O. M., Toft B., “On interval colourings of bi-regular bipartite graphs”, Ars Comb., 50 (1998), 23–32 | MR | Zbl

[18] Khachatrian H., Petrosyan P., “Interval non-edge-colorable bipartite graphs and multigraphs”, J. Graph Theory, 76:3 (2014), 200–216 | DOI | MR | Zbl

[19] Lipsky W. (Jr.), “One more polynomial complete consecutive retrieval problem”, Inf. Proc. Lett., 6:3 (1977), 91–93 | DOI | MR