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
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
