On Gupta’s Codensity Conjecture

Abstract: Let

G = (V, E)

be a multigraph. The {em cover index}

x i (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

d e l t a (G)

be the minimum degree of

G

and let

P h i (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 { m 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

x i (G) l e m i n d e l t a (G), l f l o o r P h i (G) f l o o r

. In 1978 Gupta proposed the following co-density conjecture: Every multigraph

G

satisfies

x i (G) g e m i n d e l t a (G) - 1,, l f l o o r P h i (G) f l o o r

, which is the dual version of the Goldberg-Seymour conjecture on edge-colorings of multigraphs. In this note we prove that

x i (G) g e m i n d e l t a (G) - 1,, l f l o o r P h i (G) f l o o r

if

P h i (G)

is not integral and

x i (G) g e m i n d e l t a (G) - 2,, l f l o o r P h i (G) f l o o r - 1

otherwise. We also show that this co-density conjecture implies another conjecture concerning cover index made by Gupta in 1967.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: On Gupta’s Codensity Conjecture