✦ LIBER ✦
Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
✍ Scribed by A. V. Pyatkin
- Publisher
- John Wiley and Sons
- Year
- 2004
- Tongue
- English
- Weight
- 80 KB
- Volume
- 47
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
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 (α, β)‐biregular if each vertex in A has degree α and each vertex in B has degree β. 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. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 122–128, 2004