CARMA Discrete Mathematics Instructional Seminar

3:00 pm

Thursday, 25th Oct 2012

V129, Mathematics Building

Prof. Brian Alspach

(CARMA, The University of Newcastle)

Gallai's 1966 conjecture on path decompositions

In 1966 Gallai conjectured that a connected graph of order n can be decomposed into n/2 or fewer paths when n is even, or (n+1)/2 or fewer paths when n is odd. We shall discuss old and new work on this as yet unsolved conjecture.