A Note on Interval Edge-colorings of Graphs

Authors

  • Rafayel R. Kamalian Institute for Informatics and Automation Problems of NAS RA;Russian-Armenian University
  • Petros A. Petrosyan Institute for Informatics and Automation Problems of NAS RA;Yerevan State University

Abstract

An edge-coloring of a graph G with colors 1,…,t is called an interval t-coloring if for all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integers. In this note we prove that if a connected graph G with n vertices admits an interval t-coloring, then t≤2n - 3. We also show that if G is a connected r-regular graph with n vertices that has an interval t-coloring and n≥2r + 2, then this upper bound can be improved to 2n - 5.

Author Biographies

Rafayel R. Kamalian , Institute for Informatics and Automation Problems of NAS RA;Russian-Armenian University

Department of Applied Mathematics and Informatics, RAU

Petros A. Petrosyan, Institute for Informatics and Automation Problems of NAS RA;Yerevan State University

Department of Informatics and Applied Mathematics, YSU

References

A.S. Asratian, C.J. Casselgren, “On interval edge colorings of (α, β)-biregular bipartite graphs", Discrete Math. 307, pp. 1951-1956, 2006.

A.S. Asratian, R.R. Kamalian, “Interval colorings of edges of a multigraph", Appl. Math. 5, pp. 25-34, 1987.

A.S. Asratian, R.R. Kamalian, “Investigation on interval edge-colorings of graphs", J. Combin. Theory Ser. B62, pp. 34-43, 1994.

M.A. Axenovich, “On interval colorings of planar graphs", Congr. Numer. 159, pp. 77-94, 2002.

K. Giaro, M. Kubale, M. Malafiejski, “Consecutive colorings of the edges of general graphs", Discrete Math. 236, pp. 131-143, 2001.

R.R. Kamalian, Interval edge-colorings of graphs, Doctoral Thesis, Novosibirsk, 1990.

R.R. Kamalian, P.A. Petrosyan, “A note on upper bounds for the maximum span in interval edge-colorings of graphs", Discrete Math. 312, pp. 1393-1399, 2012.

P.A. Petrosyan, “Interval edge-colorings of complete graphs and n-dimensional cubes", Discrete Math. 310, pp. 1580-1587, 2010.

Downloads

Published

2021-12-10

How to Cite

Kamalian , R. R. ., & Petrosyan, P. A. . (2021). A Note on Interval Edge-colorings of Graphs. Mathematical Problems of Computer Science, 36, 13–16. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/261

Most read articles by the same author(s)

<< < 1 2