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 [Phi(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.
تحميل البحث