On $f$-Edge Cover-Coloring of Graphs

Huimin Song 1 and Guizhen Liu 2
1 Department of Applied Mathematics, Shandong University at Weihai, Shandong 264209, P. R. China
2 Department of Mathematics, Shandong University, Shandong 250100, P. R. China

Abstract     Full Text  PDF

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\leq f(v)\leq d(v)$ for any $v\in 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 $\chi^{'}_{fc}(G)$, is the maximum $k$ such that an $f$-edge cover-coloring with $k$ kind of colors exists. In this paper we provide a Vizing type theorem for $\chi^{'}_{fc}(G)$ which generalizes a known result. We also investigate graphs $G$ or function $f$ such that $\chi^{'}_{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.