On the chromatic index of graphs with 2m+1 vertices and 2m2 edges

被引：0

作者：

Rhee, C ^{[1
]}

机构：

[1] Eastern Kentucky Univ, Dept Math Stat & Comp Sci, Richmond, KY 40475 USA

来源：

INFORMATION PROCESSING LETTERS | 1998年 / 66卷 / 03期

关键词：

chromatic index; edge coloring; complete graphs; algorithms;

D O I：

10.1016/S0020-0190(98)00041-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Consider the chromatic index problem for K2m+1, the complete graphs with 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 proved 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 much 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.

引用

页码：115 / 118

页数：4