Abstract
An edge-coloring of a graph with colors is an interval -coloring if all colors are used, and the colors of edges incident to each vertex of are distinct and form an interval of integers. A graph is interval colorable if it has an interval -coloring for some positive integer . The problem of deciding whether a bipartite graph is interval colorable is NP-complete. The smallest known examples of interval non-colorable bipartite graphs have vertices. On the other hand it is known that the bipartite graphs on at most vertices are interval colorable. In this work we observe that several classes of bipartite graphs of small order have an interval coloring. In particular, we show that all bipartite graphs on vertices are interval colorable.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.