A Note on Edge-Cover Coloring of Nearly Bipartite Graphs

Abstract

Let \(G\) be a graph with vertex set \(V(G)\). An edge coloring \(C\) of \(G\) is called an edge-cover coloring, if for each color, the edges assigned with it form an edge cover of \(G\). The maximum positive integer \(k\) such that \(G\) has a \(k\)-edge-cover coloring is called the edge cover chromatic index of \(G\) and is denoted by \(\chi’_c(G)\). It is well known that \(\min\{d(v) – \mu(v) : v \in V(G)\} \leq \chi’_c(G) \leq \delta(G)\), where \(\mu(v)\) is the multiplicity of \(v\) and \(\delta(G)\) is the minimum degree of \(G\). If \(\chi’_c(G) = \delta(G)\), \(G\) is called a graph of CI class, otherwise \(G\) is called a graph of CII class. In this paper, we give a new sufficient condition for a nearly bipartite graph to be of CI class.