✦ LIBER ✦

Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs

✍ Scribed by Armen S. Asratian; Carl Johan Casselgren; Jennifer Vandenbussche; Douglas B. West

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 138 KB
Volume: 61
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20370

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)‐biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)‐biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3‐valent vertices and lengths in {2, 4, 6, 8}. We provide several sufficient conditions for the existence of such a subgraph. © 2009 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Interval coloring of (3,4)-biregular bip

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

✍ A. V. Pyatkin 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

## 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 (α, β)‐b