On Gupta's Co-density Conjecture

Abstract

Let $G=(V,E)$ be a multigraph. The {\em cover index} $\xi (G)$ of $G$ is the greatest integer $k$ for which there is a coloring of $E$ with $k$ colors such that each vertex of $G$ is incident with at least one edge of each color. Let $\delta (G)$ be the minimum degree of $G$ and let $\Phi (G)$ be the {\em co-density} of $G$, defined by \[Φ(G)=\min \Big\{\frac{2|E^+(U)|}{|U|+1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hskip 2mm {\rm and \hskip 2mm odd} \Big\},\] where $E^{+}(U)$ is the set of all edges of $G$ with at least one end in $U$. It is easy to see that $\xi (G)\le \min \{\delta (G),\lfloor \Phi (G)\rfloor \}$. In 1978 Gupta proposed the following co-density conjecture: Every multigraph $G$ satisfies $\xi (G)\ge \min \{\delta (G)-1,\lfloor \Phi (G)\rfloor \}$, which is the dual version of the Goldberg-Seymour conjecture on edge-colorings of multigraphs. In this note we prove that $\xi (G)\ge \min \{\delta (G)-1,\lfloor \Phi (G)\rfloor \}$ if $\Phi (G)$ is not integral and $\xi (G)\ge \min \{\delta (G)-2,\lfloor \Phi (G)\rfloor -1\}$ otherwise. We also show that this co-density conjecture implies another conjecture concerning cover index made by Gupta in 1967.