On Interval Edge Colorings of Biregular Bipartite Graphs With Small Vertex Degrees. Issue 2 (19th December 2014)

• Record Type: Journal Article
• Authors: Casselgren, Carl Johan; Toft, Bjarne
• Is Part Of: Journal of graph theory. Volume 80:Issue 2(2015)
• Page Start: 83
• Page End: 97
• Publication Date: 2014-12-19
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21841
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>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 <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2dcm3t4j" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21841:jgt21841-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>a</mml:mi><mml:mo>, </mml:mo><mml:mi>b</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>‐biregular if every vertex in one part has degree <italic>a</italic> and every vertex in the other part has degree <italic>b</italic>. 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.</p> </abstract>