Interval edge colorings of (a,b)-biregular bipartite graphs

Graphs, Hypergraphs, and Computing

13 March 14:00 - 15:00

Carl Johan Casselgren - Linköping University

An interval edge coloring of a graph is a proper edge coloring by positive integers such that the colors on the edges incident to any vertex are consecutive. A bipartite graph is (a,b)-biregular if the vertices in one part all have degree a and the vertices in the other part all have degree b; it has been conjectured that all such graphs have interval edge colorings. It is known that all (2,b)-biregular graphs have interval edge colorings; the first open case is (a, b) = (3, 4). I shall discuss various results concerning this conjecture. In particular, I will give a short argument proving that all (3,6)-biregular graphs admit interval edge colorings. This is joint work with Bjarne Toft.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to