ON THE CHROMATIC INDEX OF GRAPHS WITH 2M+1 VERTICES AND 2M(2) EDGES

Authors
RHEE C
Citation
C. Rhee, ON THE CHROMATIC INDEX OF GRAPHS WITH 2M+1 VERTICES AND 2M(2) EDGES, Information processing letters, 66(3), 1998, pp. 115-118
Citations number
3
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
66
Issue
3
Year of publication
1998
Pages
115 - 118
Database
ISI
SICI code
0020-0190(1998)66:3<115:OTCIOG>2.0.ZU;2-M
Abstract
Consider the chromatic index problem for K2m+1, the complete graphs wi th 2m + 1 vertices, m =1,2,.... The chromatic index of these graphs is known to be 2m + 1, the degree of the graphs plus one. Plantholt prov ed that K2m+1 - m, the graph obtained after removing arbitrary m edges from K2m+1, has the chromatic index 2m. In this paper, we present a m uch simpler constructive proof for this problem as well as an O(m(2)) optimal time algorithm for actually assigning colors to the edges. (C) 1998 Elsevier Science B.V. All rights reserved.