Some results about f‐critical graphs
Guizhen Liu, Jianfeng Hou, Jiansheng Cai · Networks · 2007
Abstract An f‐coloring of a multigraph G is a coloring of the edges of E such that each color appears at each vertex v ∈ V at most f(v) times. The minimum number of colors needed to f‐color G is called the f‐chromatic index of G and is denoted by χ′f(G). Various scheduling problems on networks are reduced to finding an f‐coloring of a multigraph. Any simple graph G has f‐chromatic index equal to Δf(G) or Δf(G)+ 1, where Δf(G) = max v∈V{⌈ ${d(v)\over f(v)}$ ⌉} and d(v) is the degree of vertex v. A connected graph G is called f‐critical if χ′f(G)=Δf(G)+1 and χ′f(G)=Δf(G−e) < χ′f(G) for any edge e ∈ E. Some results about f‐critical graphs are given. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(3), 197–202 2007