THE CHROMATIC INDEX OF COMPLETE MULTIPARTITE GRAPHS

被引：48

作者：

HOFFMAN, DG

RODGER, CA

机构：

[1] Department of Algebra, Combinatorics and Analysis Auburn University Auburn, Alabama

来源：

JOURNAL OF GRAPH THEORY | 1992年 / 16卷 / 02期

关键词：

D O I：

10.1002/jgt.3190160207

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that a complete multipartite graph is class one if and only if it is not overfull, thus determining its chromatic index.

引用

页码：159 / 163

页数：5

共 12 条

[1]

BONDY JA, 1976, GRAPH THEORY APPLICA

[2] CRITICAL STAR MULTIGRAPHS [J].

CHETWYND, AG ;

HILTON, AJW .

GRAPHS AND COMBINATORICS, 1986, 2 (03) :209-221

[3]

CHETWYND AG, 1985, P LOND MATH SOC, V50, P193

[4] ON THE DELTA-SUBGRAPH OF GRAPHS WHICH ARE CRITICAL WITH RESPECT TO THE CHROMATIC INDEX [J].

CHETWYND, AG ;

HILTON, AJW ;

HOFFMAN, DG .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (02) :240-245

[5]

de Werra D., 1971, INFOR, V9, P220

[6]

FOURNIER JC, 1977, J MATH PURE APPL, V56, P437

[7] CLASS-ONE GRAPHS [J].

HOFFMAN, DG ;

RODGER, CA .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1988, 44 (03) :372-376

[8] THE NP-COMPLETENESS OF EDGE-COLORING [J].

HOLYER, I .

SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720

[9]

KONIG D, 1950, THEORIE ENDLICHEN UN

[10]

McDiarmid C.J.H., 1972, J I MATH APPL, V9, P23

← 1 2 →