A note on the strong chromatic index of bipartite graphs

被引：22

作者：

Nakprasit, K. ^{[1
]}

机构：

[1] Khon Kaen Univ, Khon Kaen 40002, Thailand

来源：

DISCRETE MATHEMATICS | 2008年 / 308卷 / 16期

关键词：

strong edge-coloring; induced matching;

D O I：

10.1016/j.disc.2007.07.034

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The strong chromatic index s'(G) is the minimum integer t such that there is an edge-coloring of G with t colors in which every color class is an induced matching. Brualdi and Quinn conjecture that for every bipartite graph G, s'(G) is bounded by Delta(1)Delta(2), where Delta(1) and Delta(2) are the maximum degrees among vertices in the two partite sets. We give the affirmative answer for Delta(1) = 2. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：3726 / 3728

页数：3

共 11 条

[1] THE STRONG CHROMATIC INDEX OF A CUBIC GRAPH IS AT MOST 10 [J].

ANDERSEN, LD .

DISCRETE MATHEMATICS, 1992, 108 (1-3) :231-252

[2]

BERMOND JC, 1983, LECT NOTES SERIES, V92, P1

[3] INCIDENCE AND STRONG EDGE COLORINGS OF GRAPHS [J].

BRUALDI, RA ;

MASSEY, JJQ .

DISCRETE MATHEMATICS, 1993, 122 (1-3) :51-58

[4] THE MAXIMUM NUMBER OF EDGES IN 2K2-FREE GRAPHS OF BOUNDED DEGREE [J].

CHUNG, FRK ;

GYARFAS, A ;

TUZA, Z ;

TROTTER, WT .

DISCRETE MATHEMATICS, 1990, 81 (02) :129-135

[5]

Erdos P., 1989, IRREGULARITIES PARTI, P83

[6] INDUCED MATCHINGS IN BIPARTITE GRAPHS [J].

FAUDREE, RJ ;

GYARFAS, A ;

SCHELP, RH ;

TUZA, Z .

DISCRETE MATHEMATICS, 1989, 78 (1-2) :83-87

[7] INDUCED MATCHINGS IN CUBIC GRAPHS [J].

HORAK, P ;

QING, H ;

TROTTER, WT .

JOURNAL OF GRAPH THEORY, 1993, 17 (02) :151-160

[8]

Quinn JJ, 1998, ARS COMBINATORIA, V49, P155

[9]

Quinn JJ, 1997, J GRAPH THEOR, V24, P267, DOI 10.1002/(SICI)1097-0118(199703)23:3<267::AID-JGT8>3.3.CO

[10]

2-P

← 1 2 →