Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs

摘要

An interval coloring of a graph is a proper edge coloring such that the set of used colors at every vertex is an interval of integers. Generally, it is an NP-hard problem to decide whether a graph has an interval coloring or not. A bipartite graph G =(A, B; E) is (alpha,beta)-biregular if each vertex in A has degree alpha and each vertex in B has degree beta. In this paper we prove that if the (3,4)-biregular graph G has a cubic subgraph covering the set B then G has an interval coloring. (C) 2004 Wiley Periodicals, Inc.