2015 | OriginalPaper | Buchkapitel
Edge-Colorings of Weighted Graphs
(Extended Abstract)
Autoren: Yuji Obata, Takao Nishizeki
Verlag: Springer International Publishing
Let
G
be a graph with a positive integer weight
ω
(
v
) for each vertex
v
. One wishes to assign each edge
e
of
G
a positive integer
f
(
e
) as a color so that
ω
(
v
) ≤ |
f
(
e
) −
f
(
e
′
)| for any vertex
v
and any two edges
e
and
e
′
incident to
v
. Such an assignment
f
is called an
ω
-edge-coloring of
G
, and the maximum integer assigned to edges is called the span of
f
. The
ω
-chromatic index of
G
is the minimum span over all
ω
-edge-colorings of
G
. In the paper, we present various upper and lower bounds on the
ω
-chromatic index, and obtain three efficient algorithms to find an
ω
-edge-coloring of a given graph. One of them finds an
ω
-edge-coloring with span smaller than twice the
ω
-chromatic index.
