On ƒ-Edge Cover Coloring of Nearly Bipartite Graphs

Jinbo Li ; Guizhen Liu

Bulletin of the Malaysian Mathematical Society, Tome 34 (2011) no. 2

Résumé

Let $G(V, E)$ be a graph, and let $f$ be an integer function on $V$ with $1\leq f(v)\leq d(v)$ to each vertex $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 number of colors needed to $f$-edge cover color $G$. It is well-known that $\min\limits _{v\in V}\left\lfloor \frac{d(v)-\mu(v)}{f(v)}\right\rfloor\leq\chi '_{fc}(G)\leq\delta_{f},$ where $\mu(v)$ is the multiplicity of $v$ and $\delta_{f}=\min\{\lfloor \frac{d(v)}{f(v)}\rfloor: v\in V(G)\}$. If $\chi '_{fc}= \delta_{f}$, then $G$ is of $f_{c}$-class $1$, otherwise $G$ is of $f_{c}$-class $2$. In this paper, we give some new sufficient conditions for a nearly bipartite graph to be of $f_{c}$-class $1$.

Détail

Classification : 05C15, 05C25.