Strong Chromatic Index of 2-Degenerate Graphs

被引：23

作者：

Chang, Gerard Jennhwa ^{[1
,2
,3
]}

Narayanan, N. ^{[1
]}

机构：

[1] Natl Taiwan Univ, Dept Math, Taipei 10764, Taiwan

[2] Natl Taiwan Univ, Taida Inst Math Sci, Taipei 10764, Taiwan

[3] Taipei Off, Natl Ctr Theoret Sci, Taipei, Taiwan

来源：

JOURNAL OF GRAPH THEORY | 2013年 / 73卷 / 02期

关键词：

strong chromatic index; induced matching; 2-degenerate graph; edge coloring; block line critical graph; chordless graph; BIPARTITE GRAPHS;

D O I：

10.1002/jgt.21646

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that the strong chromatic index of a 2-degenerate graph is linear in the maximum degree . This includes the class of all chordless graphs (graphs in which every cycle is induced) which in turn includes graphs where the cycle lengths are multiples of four, and settles a problem by Faudree et al. (Ars Combin 29(B) (1990), 205211). (c) 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 119126, 2013

引用

页码：119 / 126

页数：8

共 17 条

[1]

Bollobas B., 2004, Extremal Graph Theory

[2]

Borozan V., 2013, FURTHER RESULTS STRO

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

BRUALDI, RA ;

MASSEY, JJQ .

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

[4]

DIRAC GA, 1967, J REINE ANGEW MATH, V228, P204

[5]

FAUDREE RJ, 1990, ARS COMBINATORIA, V29B, P205

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

FAUDREE, RJ ;

GYARFAS, A ;

SCHELP, RH ;

TUZA, Z .

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

[7]

Leveque B., GRAPHS NO INDUCED SU

[8]

Luo R., NOTE STRONG EDGE COL

[9]

Mahdian M, 2000, RANDOM STRUCT ALGOR, V17, P357, DOI 10.1002/1098-2418(200010/12)17:3/4<357::AID-RSA9>3.0.CO

[10]

2-Y

← 1 2 →