CARMA Discrete Mathematics Instructional Seminar
3:00 pm
Thursday, 25th Oct 2012
V129, Mathematics Building
• Download Gallai's 1966 conjecture on path decompositions ("The University of Newcastle") [1]
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.