Colloquium Announcement
Department of Mathematics
West Virginia University
for
Thursday, October 1,1998, at 3:45pm
in 315 Armstrong Hall
(Tea and cookies begin at 3:00 in coffee room.)
Professor Cunquan Zhang
WVU
Edge-coloring, cycle cover and Fulkerson Conjecture
The talk will be suitable for a general audience.
Students are strongly encouraged to participate.
Abstract
Let G be a graph.
An edge-coloring of G is a coloring of the edge set of G
such that every pair of adjacent edges are
colored differently.
It is known that not every 3-regular graph is
edge-3-colorable.
The following is one the most well-known open
problem in graph theory:
Fulkerson Conjecture.
Let G be a bridgeless 3-regular graph.
Then 2G is edge-6-colorable,
where, 2G is the graph obtained from G
by replaying each edge with
a pair of parallel edges.
In this talk, we will present a few
approaches to this open problem,
such as, multi-edge-coloring,
perfect matching cover and matching cover,
even subgraph cover, etc.
A few relaxations of the conjecture will also be presented.
The information on the future (and past) Colloquia can be also found on web at the
address:
http://www.math.wvu.edu/homepages/kcies/colloquium.html