Home | People | Seminar | Working Group | Conferences | Resources

Abstract

Title: THE CYCLE PLUS TRIANGLES THEOREM AND (SOME OF) ITS IMPLICATIONS

Abstract: The Cycles plus Triangles Problem, formulated originally by Du and Hsu and sharpened by the late 'Uncle Paul' (Erdos), considers 4- regular graphs decomposable into a Hamiltonian cycle and (disjoint) triangles. Du and Hsu conjectured that the independence number of such graphs is n/3 (where n is the number of vertices), whereas Erdos conjectured that such graphs are even 3-colorable. Stiebitz and the speaker proved Erdos conjecture by using a result of Alon -Tarsi and by showing that the number of eulerian orientations in such graphs is = 2 (mod 4). This latter result suffices to prove the conjecture by Du and Hsu.
We discuss generalizations and applications of the Cycle plus Triangles Theorem w.r.t. colorability, independence number, integer flows, and cycle double covers.

Return to the seminar page.



Home | People | Seminar | Working Group | Conferences | Resources

Please send comments about this page to Maurice Rojas at rojas@math.tamu.edu.
Last Modified on 25/Feb/02