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
Adam Mickiewicz University
Technical University of Denmark, DTU