Title: Proof of the Bollobas-Catlin-Eldridge conjecture
Speaker: Gabor Kun, Rutgers University and IAS
Date: Thursday, April 8, 2010 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
We say that the graphs G and H with n vertices pack if G and H can be placed on a common set of n vertices with no common edges. Bollobas, Eldridge and independently Catlin conjectured that if that if (M(G)+1)(M(H)+1) < n+2 holds for the maximal degrees M(G) and M(H), then G and H pack. Aigner and Brandt and independently Alon and Fischer proved this in the case M(G),M(H)<3; Csaba, Shokoufandeh and Szemeredi if M(G),M(H)<4; Bollobas, Kostochka and Nakprasit proved it in case one of the graphs is degenerate; and Kaul, Kostochka and Yu showed that if M(G)M(H)<3/5n and the maximal degrees are large enough then G and H pack. We prove the conjecture for graphs with at least 108 vertices. I will spend most of the time with the proof.