Edge coloring Regular Graphs of High Degree

L. Perkovic, B. Reed

IBP-EC 1995/13: Rapport de Recherche EC / EC research reports
16 pages - Janvier/January 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Edge coloring Regular Graphs of High Degree

Résumé : Nous présentons des résultats sur la conjecture suivante : Si G est un graphe avec 2k sommets dans lequel chaque sommet a un degré r „k alors x'(OE) = r .

Abstract : We discuss the following conjecture : If G = (V,E) is a D-regular simple graph with an even number of vertices at most 2D then G is D edge colorable.
In this paper we show that the conjecture is true for large graphs if ‡V/< (2 - OE)D . We discuss related results.

Publications internes EC 1995 / EC research reports 1995