Authors
Citation
B. Reed, Edge coloring nearly bipartite graphs, OPER RES L, 24(1-2), 1999, pp. 11-14
Citations number
10
Categorie Soggetti
Engineering Mathematics
Journal title
OPERATIONS RESEARCH LETTERS
ISSN journal
01676377
→ ACNP
Volume
24
Issue
1-2
Year of publication
1999
Pages
11 - 14
Database
ISI
SICI code
0167-6377(199902/03)24:1-2<11:ECNBG>2.0.ZU;2-1
Abstract
We give a simple polynomial time algorithm to compute the chromatic index o
f graphs which can be made bipartite by deleting a vertex. An analysis of t
his algorithm shows that for such graphs, the chromatic index is the roundu
p of the fractional chromatic index. (C) 1999 Published by Elsevier Science
B.V. All rights reserved.