Computer Science – Discrete Mathematics
Scientific paper
2009-11-27
Computer Science
Discrete Mathematics
7 pages
Scientific paper
An edge coloring of a graph $G$ with colors $1,2,..., t$ is called an interval $t$-coloring if for each $i\in \{1,2,...,t\}$ there is at least one edge of $G$ colored by $i$, the colors of edges incident to any vertex of $G$ are distinct and form an interval of integers. In 1994 Asratian and Kamalian proved that if a connected graph $G$ admits an interval $t$-coloring, then $t\leq (d+1) (\Delta -1) +1$, and if $G$ is also bipartite, then this upper bound can be improved to $t\leq d(\Delta -1) +1$, where $\Delta$ is the maximum degree in $G$ and $d$ is the diameter of $G$. In this paper we show that these upper bounds can not be significantly improved.
Kamalian Rafael R.
Petrosyan Petros A.
No associations
LandOfFree
A note on upper bounds for the maximum span in interval edge colorings of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A note on upper bounds for the maximum span in interval edge colorings of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on upper bounds for the maximum span in interval edge colorings of graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-195696