图的f-边覆盖染色

宋慧敏;刘桂真

数学学报 ›› 2005, Vol. 48 ›› Issue (5) : 919-928.

PDF(555 KB)
PDF(555 KB)
数学学报 ›› 2005, Vol. 48 ›› Issue (5) : 919-928. DOI: 10.12386/A2005sxxb0111
论文

图的f-边覆盖染色

    宋慧敏;刘桂真
作者信息 +

On f-Edge Cover-Coloring of Graphs

    Hui Min SONG(2), Guio Zheng LI
Author information +
文章历史 +

摘要

设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-边覆盖染色的变型,提出了一些可进一步研究的问题.

Abstract

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(v) ≤ d(v) for any v ∈ V. An f-edge cover-coloring is an edge coloring C such that each color appears at each vertex v at least f(v) times. The f-edge cover chromatic index of G, denoted by X'fc(G), is the maximum k such that an f-edge cover k-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

关键词

f-边覆盖染色 / 边染色 / 多重图

引用本文

导出引用
宋慧敏;刘桂真. 图的f-边覆盖染色. 数学学报, 2005, 48(5): 919-928 https://doi.org/10.12386/A2005sxxb0111
Hui Min SONG(2), Guio Zheng LI. On f-Edge Cover-Coloring of Graphs. Acta Mathematica Sinica, Chinese Series, 2005, 48(5): 919-928 https://doi.org/10.12386/A2005sxxb0111
PDF(555 KB)

377

Accesses

0

Citation

Detail

段落导航
相关文章

/