Title:
On Interval Cyclic Colorings of Bipartite Graphs
Author:
Type:
Co-author(s) :
Casselgren Carl J. ; Petrosyan Petros
Uncontrolled Keywords:
Edge-coloring ; interval coloring ; interval cyclic coloring ; bipartite graph ; biregular bipartite graph
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)}.
Language:
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:
Year:
Time period:
Conference title:
10 th International Conference on Computer Science and Information Technologies CSIT 2015