On Interval Edge Colorings of Biregular Bipartite Graphs With Small Vertex Degrees
Carl Johan Casselgren, Bjarne Toft · Journal of Graph Theory · 2014
Abstract A proper edge coloring of a graph with colors 1, 2, 3, … is called an interval coloring if the colors on the edges incident to each vertex form an interval of integers. A bipartite graph is ‐biregular if every vertex in one part has degree a and every vertex in the other part has degree b. It has been conjectured that all such graphs have interval colorings. We prove that all (3, 6)‐biregular graphs have interval colorings and that all (3, 9)‐biregular graphs having a cubic subgraph covering all vertices of degree 9 admit interval colorings. Moreover, we prove that slightly weaker versions of the conjecture hold for (3, 5)‐biregular, (4, 6)‐biregular, and (4, 8)‐biregular graphs. All our proofs are constructive and yield polynomial time algorithms for constructing the required colorings.