# A Note on Interval Edge-colorings of Graphs

## 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.

## 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

## How to Cite

*Mathematical Problems of Computer Science*,

*36*, 13–16. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/261

## Issue

## Section

## License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.