Edge covering coloring and fractional edge covering coloring (Q698408): Difference between revisions

For a graph \(G\) a subset of edges \(S\subseteq E(G)\) is called an edge cover of \(G\) if every vertex of \(G\) is an end vertex of some edge in \(S\). The edge covering chromatic number of a graph \(G\), denoted by \(\chi '_{c}(G)\), is the maximum size of a partition of \(E(G)\) into edge covers of \(G\). It is known that for any graph \(G\) with minimum degree \(\delta \), \(\delta -1\leq \chi '_{c}(G)\leq \delta \) holds. The fractional edge covering chromatic number of a graph \(G\), denoted by \(\chi '_{cf}(G)\), is the fractional matching number of the edge covering hypergraph \({\mathcal H}\) of \(G\), whose vertices are the edges of \(G\) and whose hyperedges are all edge covering subsets of \(E(G)\). In this paper the relation between \(\chi '_{c}(G)\) and \(\delta \) is studied and a new proof of the inequalities \(\delta -1\leq \chi '_{c}(G)\leq \delta \) is given by using some graph coloring techniques. Also, for any graph \(G\) it is shown that \(\chi '_{cf}(G)=\min \{\delta, \lambda (G)\}\), where \(\lambda (G)=\min _{S}|C[S]|/\lceil|S|/2\rceil \), and the minimum is taken over all nonempty subsets \(S\) of \(V(G)\) and \(C[S]\) is the set of edges that have at least one end in \(S\).