| ABSTRACT: |
By an old result of Vizing, the chromatic
index
(that is, the
minimal number of colors needed to color the edges of the graph so that
no
two adjacent edges are of the same color) is either k or k+1, where k
is
the maximal valency of a vertex in the graph. In the first case, the
graph
is said to be of Class 1. In general, deciding whether a given graph is
of
Class 1 or not is an NP-complete problem. However, for certain families
of graphs, it has been either shown or conjectured that they all belong
to
Class 1. For example, Robertson, Sanders, Seymour, and Thomas proved
that
every 3-valent 2-connected graph without a Petersen minor is
3-edge-colorable, and thus belongs to Class 1.
In this talk, I will present a recent result, which shows that every
connected 3-valent vertex-transitive graph whose automorphism group
contains a solvable vertex-transitive subgroup is 3-edge-colorable,
with the sole exception of the Petersen graph. I will also pose a few
yet unanswered questions. |