TY - GEN

T1 - Simple reduction of f-colorings to edge-colorings

AU - Zhou, Xiao

AU - Nishizeki, Takao

N1 - Publisher Copyright:
© 1995, Springer-Verlag. All Rights Reserved.

PY - 1995

Y1 - 1995

N2 - In an edge-coloring of a graph G = (V, E) each color appears around each vertex at most once. An f-coloring is a generalization of an edge-coloring in which each color appears around each vertex v at most f(υ) times where f is a function assigning a natural number f(υ) ∊ N to each vertex υ ∊ V. In this paper we first give a simple reduction of the f-coloring problem to the ordinary edge-coloring problem, that is, we show that, given a graph G = (V, E) and a function f: υ → N, one can directly construct in polynomial-time a new simple graph whose edge-coloring using a minimum number of colors immediately induces an f-coloring of G using a minimum number of colors. As by-products, we give a necessary and sufficient condition for a graph to have an f-factorization, and show that the edge-coloring problem for multigraphs can be easily reduced to edge-coloring problems for simple graphs.

AB - In an edge-coloring of a graph G = (V, E) each color appears around each vertex at most once. An f-coloring is a generalization of an edge-coloring in which each color appears around each vertex v at most f(υ) times where f is a function assigning a natural number f(υ) ∊ N to each vertex υ ∊ V. In this paper we first give a simple reduction of the f-coloring problem to the ordinary edge-coloring problem, that is, we show that, given a graph G = (V, E) and a function f: υ → N, one can directly construct in polynomial-time a new simple graph whose edge-coloring using a minimum number of colors immediately induces an f-coloring of G using a minimum number of colors. As by-products, we give a necessary and sufficient condition for a graph to have an f-factorization, and show that the edge-coloring problem for multigraphs can be easily reduced to edge-coloring problems for simple graphs.

UR - http://www.scopus.com/inward/record.url?scp=21844511060&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21844511060&partnerID=8YFLogxK

U2 - 10.1007/BFb0030836

DO - 10.1007/BFb0030836

M3 - Conference contribution

AN - SCOPUS:21844511060

SN - 354060216X

SN - 9783540602163

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 223

EP - 228

BT - Computing and Combinatorics - 1st Annual International Conference, COCOON 1995, Proceedings

A2 - Du, Ding-Zhu

A2 - Li, Ming

A2 - Du, Ding-Zhu

PB - Springer Verlag

T2 - 1st Annual International Computing and Combinatorics Conference, COCOON 1995

Y2 - 24 August 1995 through 26 August 1995

ER -