Co-author(s) :

Casselgren Carl J. ; Petrosyan Petros

Abstract:

A proper edge-coloring of a graph G with colors 1, . . . , t is called an interval (interval cyclic) t-coloring if all colors are used, and the edges incident to each vertex v 2 V (G) are colored by dG(v) consecutive colors (modulo t), where dG(v) is the degree of a vertex v in G. A graph G is interval (interval cyclically) colorable if it has an interval (interval cyclic) t-coloring for some positive integer t. An (a, b)-biregular bipartite graph G is a bipartite graph G with the vertices in one part all having degree a and the vertices in the other part all having degree b. In 1995, Toft conjectured that all biregular bipartite graphs are interval colorable. This conjecture remains open even for (4, 3)-biregular bipartite graphs. Recently, Casselgren and Toft suggested the following weaker version of the Toft’s conjecture: all biregular bipartite graphs are interval cyclically colorable. They also proved this conjecture for all (8, 4)- biregular bipartite graphs. In this paper we prove the last conjecture for all (a, b)-biregular bipartite graphs when (a, b) 2 {(5, 3), (6, 4), (7, 4), (8, 6)}.

Identifier:

oai:noad.sci.am:135973

Language:

English

URL:

Additional Information:

armen.asratian@liu.se ; carl.johan.casselgren@liu.se ; pet petros@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems ; Linkoping University ; Department of 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