•
On ƒ-Edge Cover Coloring of Nearly Bipartite Graphs
Jinbo Li and Guizhen Liu
Abstract.
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\).
2010 Mathematics Subject Classification: 05C15, 05C25.
Full text: PDF
|
