Premium
On Interval Edge Colorings of Biregular Bipartite Graphs With Small Vertex Degrees
Author(s) -
Casselgren Carl Johan,
Toft Bjarne
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21841
Subject(s) - combinatorics , mathematics , bipartite graph , edge coloring , vertex (graph theory) , discrete mathematics , complete coloring , pathwidth , constructive , conjecture , graph , graph power , line graph , computer science , process (computing) , operating system
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 ( a , b ) ‐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.