Title:
Interval Edge-Colorings with Gaps of Bipartite Graphs
Author:
Type:
Uncontrolled Keywords:
interval coloring ; near-interval coloring ; bipartite graph ; biregular bipartite graph ; hypercube
Abstract:
An interval (t, h)-coloring (h e Z + ) o f a graph G is a proper edge-coloring a o f G with colors 1 , . . . , t such that all colors are used, and the colors o f edges incident to each vertex v satisfy the condition dG (v) — 1 < S (v, a) — S (v, a) < dG (v) + h — 1, where dG (v) is the degree o f a vertex v in G, S (v, a) is the set o f colors o f edges incident to v, and S (v, a) and S (v, a ) are the smallest and largest colors o f S (v ,a ) , respectively. In this paper we investigate interval (t, h )-colorings o f bipartite graphs. In particular, we prove that: 1) if G is a bipartite graph with A (G ) = 4, then G has an interval (4 ,1)-coloring; 2) if G is a bipartite graph with A (G ) = 5 and without a vertex o f degree 3, then G has an interval (5 ,1)-coloring; 3) if G is a bipartite graph with A (G ) = 6 and it has a 2-factor, then G has an interval (6 ,1)-coloring. We also obtain some results on interval (t, h)-colorings o f biregular bipartite graphs and hypercubes.
Language:
URL:
Additional Information:
Affiliation:
Institute for Informatics and Automation Problems ; Yerevan State University ; Department of informatics and applied mathematics
Country:
Year:
Time period:
Conference title:
10 th International Conference on Computer Science and Information Technologies CSIT 2015