Title: THE CYCLE PLUS TRIANGLES THEOREM AND (SOME OF) ITS
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.
Please send comments about this page to Maurice Rojas at firstname.lastname@example.org.
Last Modified on 25/Feb/02