Proper Path-Factors and Interval Edge-Coloring of (3,4)-Biregular Bigraphs

被引：17

作者：

Asratian, Armen S. ^{[1
]}

Casselgren, Carl Johan ^{[2
]}

Vandenbussche, Jennifer ^{[3
]}

West, Douglas B. ^{[4
]}

机构：

[1] Linkoping Univ, Linkoping, Sweden

[2] Umea Univ, Umea, Sweden

[3] So Polytech State Univ, Marietta, GA USA

[4] Univ Illinois, Urbana, IL 61801 USA

来源：

JOURNAL OF GRAPH THEORY | 2009年 / 61卷 / 02期

关键词：

path factor; interval edge-coloring; biregular bipartite graph; BIPARTITE GRAPHS;

D O I：

10.1002/jgt.20370

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 61: 88-97, 2009

引用

页码：88 / 97

页数：10

共 16 条

[1]

Asratian A.S., 1987, Appl. Math., V5, P25

[2] On interval edge colorings of (α, β)-biregular bipartite graphs [J].