Circular edge-colorings of graphs with large girth
摘要
Several relaxation of graph coloring have been introduced
and intensively studied, including a notion of circular coloring.
A proper circular k-edge-coloring, for a real
k ³ 1
, is a
coloring by real numbers from the interval [0,k) such that the
difference modulo k of the colors c1 and c2 assigned to
incident edges is at least one, i.e.,
1
£
|c1-c2|
£
k-1.
We
show that for each
e
> 0
and each integer
D
³
1, there
exists a number g such that for any graph G of maximum degree D
and girth at least g, the circular chromatic index of G is at
most D+epsilon. One of motivations for our research was a
conjecture of Jaeger and Swart from 1979 that high girth cubic
graphs have chromatic index three. The conjecture was disproved
by Kochol in 1996, but our results imply that the conjecture is
(almost) true when relaxed to circular colorings. At the end of
the talk, we also briefly mention new results on the circular
chromatic index of flower snarks and cubic graphs of large odd
girth.
∼Daniel Kral 教授演講摘要∼