Interval edge-colorings of cubic graphs

Details Interval edge-colorings of cubic graphs Interval edge-colorings of cubic graphs

2011-10-06

arxiv.org/abs/1110.1161v1

Proceedings of the CSIT Conference, Yerevan, 2011, pp. 86-88

Computer Science

Discrete Mathematics

3 pages

Scientific paper

An edge-coloring of a multigraph G with colors 1,2,...,t is called an interval t-coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In this paper we prove that if G is a connected cubic multigraph (a connected cubic graph) that admits an interval t-coloring, then t\leq |V(G)| +1 (t\leq |V(G)|), where V(G) is the set of vertices of G. Moreover, if G is a connected cubic graph, G\neq K_{4}, and G has an interval t-coloring, then t\leq |V(G)| -1. We also show that these upper bounds are sharp. Finally, we prove that if G is a bipartite subcubic multigraph, then G has an interval edge-coloring with no more than four colors.

Affiliated with

Also associated with

No associations

Rating

Interval edge-colorings of cubic 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 Interval edge-colorings of cubic graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interval edge-colorings of cubic graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-180931