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.

Identifier:

oai:noad.sci.am:135982

Language:

English

URL:

Additional Information:

pet petros@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems ; Yerevan State University ; Department of informatics and applied mathematics

Country:

Armenia

Year:

2015

Time period:

September 28 - October 2

Conference title:

10 th International Conference on Computer Science and Information Technologies CSIT 2015

Place:

Yerevan

Participation type:

oral