The strong chromatic index of (3, Δ)-bipartite graphs

被引：14

作者：

Huang, Mingfang ^{[1
]}

Yu, Gexin ^{[2
]}

Zhou, Xiangqian ^{[3
]}

机构：

[1] Wuhan Univ Technol, Sch Sci, Dept Math, Wuhan, Peoples R China

[2] Coll William & Mary, Dept Math, Williamsburg, VA 23185 USA

[3] Wright State Univ, Dept Math & Stat, Dayton, OH 45435 USA

来源：

DISCRETE MATHEMATICS | 2017年 / 340卷 / 05期

关键词：

Bipartite graph; Strong edge-coloring; Induced matching;

D O I：

10.1016/j.disc.2016.10.016

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A strong edge-coloring of a graph G = (V, E) is a partition of its edge set E into induced matchings. We study bipartite graphs with one part having maximum degree at most 3 and the other part having maximum degree Delta. We show that every such graph has a strong edge-coloring using at most 3 Delta colors. Our result confirms a conjecture of Brualdi and Quinn Massey (1993) for this class of bipartite graphs. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：1143 / 1149

页数：7

共 7 条

[1] Strong edge-coloring of (3, Δ)-bipartite graphs
Bensmail, Julien
Lagoutte, Aurelie
Valicov, Petru
[J]. DISCRETE MATHEMATICS, 2016, 339 (01) : 391 - 398
[2] INCIDENCE AND STRONG EDGE COLORINGS OF GRAPHS
BRUALDI, RA
MASSEY, JJQ
[J]. DISCRETE MATHEMATICS, 1993, 122 (1-3) : 51 - 58
[3] Erdos P., 1989, Irregularities of partitions, Algorithms and Combinatorics: Study and Research Texts, V8, P162
[4] FAUDREE RJ, 1990, ARS COMBINATORIA, V29B, P205
[5] Fouquet J.L., 1983, ARS COMBIN A, V16A, P141, DOI DOI 10.1090/S0894-0347-1992-1124979-1
[6] A note on the strong chromatic index of bipartite graphs
Nakprasit, K.
[J]. DISCRETE MATHEMATICS, 2008, 308 (16) : 3726 - 3728
[7] ON INDUCED MATCHINGS
STEGER, A
YU, ML
[J]. DISCRETE MATHEMATICS, 1993, 120 (1-3) : 291 - 295

← 1 →