图的f-边覆盖染色

On f-Edge Cover-Coloring of Graphs

设G(V,E)是至少含有一条边的无环图,f厂是定义在V上的整值函数且对任意的v∈V,有1≤f(v)≤d(v).若边染色C使所用的每一种颜色在任一顶点v上至少出现f(v)次,则称该染色C为,f-边覆盖染色.能对图G进行,f-边覆盖k-边染色的最大颜色数k,称为图G的,f-边覆盖色数,记为X'fc(G).本文提供了一个关于X'fc(G)的Vizing型定理,使一些已有重要结论得以推广;研究了一些使X'fc(G)达到该Vizing型定理上界的几类图或函数f,还讨论了f-边覆盖染色的变型,提出了一些可进一步研究的问题.

Let G（V, E） be a loop-less graph with at least one edge, and let f be an integer function on V such that 1 ≤ f（υ） ≤d（υ） for any υ ∈ V. An f-edge cover-coloring is an edge coloring C such that each color appears at each vertex v at least f（υ） times. The f-edge cover chromatic index of G, denoted by X＇fc（G）, is the maximum k such that an f-edge cover κ-edge coloring exists. In this paper we provide a Vizing type theorem for X＇fc（G） which generalizes a known result. We also investigate graph G or function f such that X＇fc（G） attains the upper bound in the Vizing type theorem. A variation of f-edge cover-coloring of graphs and some open problems are proposed.