Graph Theory » Algebraic G.T.

Matching polynomials of vertex transitive graphs ★★

Author(s): Mohar

Conjecture   For every integer $ r $ there exists a vertex transitive graph $ G $ whose matching polynomial has a root of multiplicity at least $ r $.

Keywords: matching polynomial; vertex-transitive

Posted by Robert Samal
updated April 12th, 2007
add new comment
Graph Theory » Coloring » Edge coloring

A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

Conjecture   Let $ H $ be a simple $ d $-uniform hypergraph, and assume that every set of $ d-1 $ points is contained in at most $ r $ edges. Then there exists an $ r+d-1 $-edge-coloring so that any two edges which share $ d-1 $ vertices have distinct colors.

Keywords: edge-coloring; hypergraph; Vizing

Posted by mdevos
updated June 23rd, 2009
1 comment