Examples of bipartite graphs which are not cyclically-interval colorable

R. R. Kamalian

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2019), pp. 123-126.

Résumé

A proper edge $t$-coloring of an undirected, simple, finite, connected graph $G$ is a coloring of its edges with colors $1,2,...,t$ such that all colors are used, and no two adjacent edges receive the same color. A cyclically-interval $t$-coloring of a graph $G$ is a proper edge $t$-coloring of $G$ such that for each its vertex $x$ at least one of the following two conditions holds: a) the set of colors used on edges incident to $x$ is an interval of integers, b) the set of colors not used on edges incident to $x$ is an interval of integers. For any positive integer $t$, let ${\mathfrak{M}}_t$ be the set of graphs for which there exists a cyclically-interval $t$-coloring. Examples of bipartite graphs that do not belong to the class $\bigcup _{t\ge 1}{\mathfrak{M}}_t$ are constructed.

Bibliographie

[1] Vizing V. G., “The chromatic index of a multigraph”, Kibernetika, 3 (1965), 29–39 | MR | Zbl

[2] West D. B., Introduction to Graph Theory, Prentice-Hall, New Jersey, 1996 | MR | Zbl

[3] Kamalian R. R., “On cyclically-interval edge colorings of trees”, Bul. Acad. Ştiinţe Repub. Moldova, Mat., 2012, no. 1(68), 50–58 | MR | Zbl

[4] Kamalian R. R., “On cyclically continuous edge colorings of simple cycles”, Proceedings of the CSIT Conference (Yerevan, 2007), 79–80 (in Russian)

[5] Kamalian R. R., “On a number of colors in cyclically-interval edge-colorings of simple cycles”, Open Journal of Discrete Mathematics, 3 (2013), 43–48 | DOI | MR

[6] Altinakar S., Caporossi G., Hertz A., “On compact $k$-edge-colorings: A polynomial time reduction from linear to cyclic”, Discrete Optimization, 8 (2011), 502–512 | DOI | MR | Zbl

[7] Asratian A. S., Investigation of some mathematical model of scheduling theory, Doctoral Thesis, M., 1980 (in Russian)

[8] Bartholdi J. J., Orlin J. B., Ratliff H. D., “Cyclic scheduling via integer programs with circular ones”, Operations Research, 28 (1980), 1074–1085 | DOI | MR | Zbl

[9] Dauscha W., Modrow H. D., Neumann A., “On cyclic sequence type for constructing cyclic schedules”, Zeitschrift für Operations Research, 29 (1985), 1–30 | MR | Zbl

[10] Jensen T. R., Toft B., Graph Coloring Problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995 | MR | Zbl

[11] Kamalian R. R., Interval Edge Colorings of Graphs, Doctoral dissertation, The Institute of Mathematics of the Siberian Branch of the Academy of Sciences of USSR, Novosibirsk, 1990 (in Russian)

[12] Kamalian R. R., “On the existence of bipartite graphs which are not cyclically-interval colorable”, Proceedings of the CSIT Conference (Yerevan, 2017), 203–204

[13] Kubale M., Graph Colorings, American Mathematical Society, 2004 | MR | Zbl

[14] Kubale M., Nadolski A., “Chromatic scheduling in a cyclic open shop”, European Journal of Operational Research, 164 (2005), 585–591 | DOI | MR | Zbl

[15] Nadolski A., “Compact cyclic edge-colorings of graphs”, Discrete Mathematics, 308 (2008), 2407–2417 | DOI | MR | Zbl

[16] de Werra D., Mahadev N. V. R., Solot Ph., Periodic compact scheduling, ORWP 89/18, Ecole Polytechnique Federale de Lausanne, 1989

[17] de Werra D., Solot Ph., Compact cylindrical chromatic scheduling, ORWP 89/10, Ecole Polytechnique Federale de Lausanne, 1989 | MR

[18] de Werra D., Solot Ph., “Compact cylindrical chromatic scheduling”, SIAM J. Discrete Math., 4:4 (1991), 528–534 | DOI | MR | Zbl

[19] Kotzig A., “1-factorizations of Cartesian products of regular graphs”, J. Graph Theory, 3 (1979), 23–34 | DOI | MR | Zbl

[20] Casselgren C. J., Toft B., “On interval edge colorings of biregular bipartite graphs with small vertex degrees”, J. Graph Theory, 80 (2015), 83–97 | DOI | MR | Zbl

[21] Petrosyan P. A., Mkhitaryan S. T., “Interval cyclic edge-colorings of graphs”, Discrete Math., 339 (2016), 1848–1860 | DOI | MR | Zbl

[22] Casselgren C. J., Petrosyan P. A., Toft B., “On interval and cyclic interval edge colorings of $(3,5)$-biregular graphs”, Discrete Math., 340 (2017), 2678–2687 | DOI | MR | Zbl

[23] Asratian A. S., Casselgren C. J., Petrosyan P. A., “Some results on cyclic interval edge colorings of graphs”, Journal of Graph Theory, 87 (2018), 239–252 | DOI | MR | Zbl

[24] Casselgren C. J., Khachatrian H. H., Petrosyan P. A., “Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs”, Discrete Math., 341 (2018), 627–637 | DOI | MR | Zbl