Upper bounds for the fg‐chromatic index of graphs
Shin-ichi Nakano, Takao Nishizeki, Nobuji Saito · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1989
Abstract This paper introduces a new edge‐coloring of graphs called “fg‐edge‐coloring.” It is used to color all edges of a graph so that at most f(v) edges of a same color exist among edges incident at each vertex v, and at most g(vw) edges among multiple edges joining each pair of vertices v and w. Various upper bounds are given for the fg‐chromatic index, that is, the minimum number of colors required for fg‐coloring. One of them is a generalization of the upper bounds for the ordinary edge‐coloring by Vizing and Hakimi‐Kariv. the proof is constructive and yields a polynomial time algorithm to determine fg‐coloring using colors no more than the upper bound.