Talks & Seminars
How many disjoint two edge paths must a cubic graph have?
Dhruv Mubayi, University of Illinois-Chicago
Date & Time: August 8, 2003 11:30
Venue: Seminar Hall
Let $G$ be a $d$-regular graph, and $F$ a fixed graph. We\Nconsider the following packing problem: What is the maximum number of\Npairwise vertex disjoint copies of $F$ that we can find in $G$? We focus on the case when $d=3$, and $F$ is a path with two edges, answering the question in the title. Our proof also provides a quadratic\Ntime (in the number of vertices of $G$) 3/4-approximation algorithm for this problem. Asymptotically optimal results are also provided for the more general case when $F$ is an arbitrary tree. This is joint work with Alexander Kelmans (Rutgers and Puerto Rico), and Benny Sudakov (Princeton).
Speaker Profile:
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback