Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647808 | Discrete Mathematics | 2012 | 7 Pages |
Abstract
An edge-coloring of a graph GG with colors 1,…,t1,…,t is an interval tt-coloring if all colors are used, and the colors of edges incident to each vertex of GG are distinct and form an interval of integers. In 1994, Asratian and Kamalian proved that if a connected graph GG admits an interval tt-coloring, then t≤(diam(G)+1)(Δ(G)−1)+1, and if GG is also bipartite, then this upper bound can be improved to t≤diam(G)(Δ(G)−1)+1, where Δ(G)Δ(G) is the maximum degree of GG and diam(G) is the diameter of GG. In this note, we show that these upper bounds cannot be significantly improved.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
R.R. Kamalian, P.A. Petrosyan,