图的f-边覆盖染色  

On f-Edge Cover-Coloring of Graphs

作　　者：宋慧敏[1] 刘桂真[2] 

机构地区：[1]山东大学威海分校应用数学系,威海264209 [2]山东大学系统科学与数学学院,济南250100

出　　处：《数学学报（中文版）》2005年第5期919-928,共10页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金(10471078)高等学校博士点学科专项基金山东大学威海分校基金资助项目

摘　　要：设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.

关 键 词：多重图 边染色 f-边覆盖染色 

分 类 号：O157[理学—数学]