Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Edge-Colorings of Weighted Graphs
(Extended Abstract)
verfasst von : Yuji Obata, Takao Nishizeki
Erschienen in: WALCOM: Algorithms and Computation
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.