Home » Author index

Tarsi, Michael


Graph Theory » Coloring

Coloring the union of degenerate graphs ★★

Author(s): Tarsi

Conjecture   The union of a $ 1 $-degenerate graph (a forest) and a $ 2 $-degenerate graph is $ 5 $-colourable.

Keywords:

Posted by fhavet
updated March 3rd, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

Short cycle covers ★★

Author(s): Alon; Tarsi

Conjecture   For every bridgeless graph $ G $ there is a collection of cycles in $ G $ that
  • covers every edge of $ G $ and
  • has total length at most $ \tfrac 75 |E(G)| $.

Keywords: chinese postman tour; cycle; cycle cover

Posted by Robert Samal
updated September 15th, 2008
add new comment
Combinatorics

Even vs. odd latin squares ★★★

Author(s): Alon; Tarsi

A latin square is even if the product of the signs of all of the row and column permutations is 1 and is odd otherwise.

Conjecture   For every positive even integer $ n $, the number of even latin squares of order $ n $ and the number of odd latin squares of order $ n $ are different.

Keywords: latin square

Posted by mdevos
updated October 7th, 2007
add new comment
Combinatorics » Matrices

The additive basis conjecture ★★★

Author(s): Jaeger; Linial; Payan; Tarsi

Conjecture   For every prime $ p $, there is a constant $ c(p) $ (possibly $ c(p)=p $) so that the union (as multisets) of any $ c(p) $ bases of the vector space $ ({\mathbb Z}_p)^n $ contains an additive basis.

Keywords: additive basis; matrix

Posted by mdevos
updated March 8th, 2007
add new comment
Syndicate content