On cyclically-interval edge colorings of trees

R. R. Kamalian

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2012), pp. 50-58.

Résumé

For an undirected, simple, finite, connected graph $G$, we denote by $V(G)$ and $E(G)$ the sets of its vertices and edges, respectively. A function $\varphi\colon E(G)\to\{1,2,\dots,t\}$ is called a proper edge $t$-coloring of a graph $G$ if adjacent edges are colored differently and each of $t$ colors is used. An arbitrary nonempty subset of consecutive integers is called an interval. If $\varphi$ is a proper edge $t$-coloring of a graph $G$ and $x\in V(G)$, then $S_G(x,\varphi)$ denotes the set of colors of edges of $G$ which are incident with $x$. A proper edge $t$-coloring $\varphi$ of a graph $G$ is called a cyclically-interval $t$-coloring if for any $x\in V(G)$ at least one of the following two conditions holds: a) $S_G(x,\varphi)$ is an interval, b) $\{1,2,\dots,t\}\setminus S_G(x,\varphi)$ is an interval. For any $t\in\mathbb N$, let $\mathfrak M_t$ be the set of graphs for which there exists a cyclically-interval $t$-coloring, and let $\mathfrak M\equiv\bigcup_{t\geq1}\mathfrak M_t$. For an arbitrary tree $G$, it is proved that $G\in\mathfrak M$ and all possible values of $t$ are found for which $G\in\mathfrak M_t$.

Bibliographie

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

[2] Asratian A. S., Casselgren C. J., A sufficient condition for interval edge colorings of $(4,3)$-biregular bipartite graphs, Research report LiTH-MAT-R-2006-07, Linköping University, 2006

[3] Asratian A. S., Casselgren C. J., Some results on interval edge colorings of $(\alpha,\beta)$-biregular bipartite graphs, Research report LiTH-MAT-R-2006-09, Linköping University, 2006

[4] Asratian A. S., Casselgren C. J., “On interval edge colorings of $(\alpha,\beta)$-biregular bipartite graphs”, Discrete Math., 307 (2006), 1951–1956 | DOI | MR

[5] Asratian A. S., Casselgren C. J., “On path factors of $(3,4)$-biregular bigraphs”, Graphs and Combinatorics, 24 (2008), 405–411 | DOI | MR | Zbl

[6] Asratian A. S., Casselgren C. J., Vandenbussche J., West D. B., “Proper path-factors and interval edge-coloring of $(3,4)$-biregular bigraphs”, J. Graph Theory, 61 (2009), 88–97 | DOI | MR | Zbl

[7] Asratian A. S., Denley T. M. J., Haggkvist R., Bipartite graphs and their applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, 1998 | MR | Zbl

[8] Asratian A. S., Kamalian R. R., “Interval colorings of edges of a multigraph”, Appl. Math., 5 (1987), 25–34, Yerevan State University (in Russian) | MR

[9] Asratian A. S., Kamalian R. R., “Investigation on interval edge-colorings of graphs”, J. Combin. Theory Ser. B, 62 (1994), 34–43 | DOI | MR | Zbl

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

[11] Casselgren C. J., “A note on path factors of $(3,4)$-biregular bipartite graphs”, The Electron. J. of Combinatorics, 18 (2011), P218 | MR | Zbl

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

[13] Giaro K., “The complexity of consecutive $\Delta$-coloring of bipartite graphs: 4 is easy, 5 is hard”, Ars Combin., 47 (1997), 287–298 | MR | Zbl

[14] Giaro K., Compact task scheduling on dedicated processors with no waiting periods, PhD thesis, Technical University of Gdansk, EIT faculty, Gdansk, 1999 (in Polish)

[15] Giaro K., Kubale M., Malafiejski M., “On the deficiency of bipartite graphs”, Discrete Appl. Math., 94 (1999), 193–203 | DOI | MR | Zbl

[16] Hansen H. M., Scheduling with minimum waiting periods, Master's Thesis, Odense University, Odense, Denmark, 1992 (in Danish)

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

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

[19] Kamalian R. R., Interval colorings of complete bipartite graphs and trees, Preprint, The Computing Centre of the Academy of Sciences of Armenia, Yerevan, 1989 (in Russian)

[20] 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)

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

[22] Kamalian R. R., On a number of colors in cyclically interval edge colorings of trees, Research report LiTH-MAT-R-2010/09-SE, Linköping University, 2010

[23] Kamalian R. R., “On a number of colors in cyclically continuous edge colorings of simple cycles”, The Herald of the RAU, 1, Yerevan, 2010, 13–21 (in Russian)

[24] Kamalian R. R., Mirumian A. N., “Interval edge colorings of bipartite graphs of some class”, Dokl. NAN RA, 97 (1997), 3–5 (in Russian) | MR

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

[26] Petrosyan P. A., “Interval edge-colorings of Möbius ladders”, Proceedings of the CSIT Conference, Yerevan, 2005, 146–149 (in Russian)

[27] Petrosyan P. A., “Interval edge-colorings of complete graphs and $n$-dimensional cubes”, Discrete Math., 310 (2010), 1580–1587 | DOI | MR | Zbl

[28] Petrosyan P. A., “On interval edge-colorings of multigraphs”, The Herald of the RAU, 1, Yerevan, 2011, 12–21 (in Russian)

[29] Petrosyan P. A., Arakelyan H. Z., Baghdasaryan V. M., “A generalization of interval edge-colorings of graphs”, Discrete Appl. Math., 158 (2010), 1827–1837 | DOI | MR | Zbl

[30] Pyatkin A. V., “Interval coloring of $(3,4)$-biregular bipartite graphs having large cubic subgraphs”, J. Graph Theory, 47 (2004), 122–128 | DOI | MR | Zbl

[31] Sevast'janov S. V., “Interval colorability of the edges of a bipartite graph”, Metody Diskret. Analiza, 50 (1990), 61–72 (in Russian) | MR

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

[33] de Werra D., Mahadev N. V. R., Solot Ph., Periodic compact scheduling, ORWP 89/18, Ecole Polytechnique Fédérale de Lausanne, 1989

[34] de Werra D., Solot Ph., Compact cylindrical chromatic scheduling, ORWP 89/10, Ecole Polytechnique Fédérale de Lausanne, 1989

[35] West D. B., Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, New Jersey, 1996 | MR

[36] Yang F., Li X., “Interval coloring of $(3,4)$-biregular bigraphs having two $(2,3)$-biregular bipartite subgraphs”, Appl. Math. Letters, 24 (2011), 1574–1577 | DOI | MR | Zbl