Համահեղինակ(ներ):

Casselgren Carl J. ; Petrosyan Petros

Ամփոփում:

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)}.

Նույնականացուցիչ:

oai:noad.sci.am:135973

Լեզու:

English

URL:

լրացուցիչ տեղեկատվություն:

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

Կազմակերպության անվանում:

Institute for Informatics and Automation Problems ; Linkoping University ; Department of Mathematics

Երկիր:

Armenia

Տարի:

2015

Ժամանակահատված:

September 28 - October 2

Գիտաժողովի անվանում:

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

Վայր:

Yerevan

Մասնակցության տեսակը:

oral