Department
Home Page
About Us:
• Contact Info.
• Faculty
• Staff
• Teaching Assistants
Academic Program:
• Admission
• Undergraduate
• Graduate
• Certificates
Courses:
• Course Description
• Class Web Pages
• Class Syllabi
Research:
• Colloquium
• Interdisciplinary Seminar
• Seminars
• Steve Goldman Lectures in Mathematical Physics
Links:
| • Completing Online GEP Courses |
| • Best Jobs |
| • Newsletter |
| • Math Lab |
| •Math Placement Test |
| • Careers |
| • American Mathematical Society |
| • Mathematical Association of America |
11/22/05 Colloquium
Dr. Hemanshu Kaul
University of Illinois,
Urbana-Champaign
University of Illinois,
Urbana-Champaign
Graph Packing - Conjectures and Results
Abstract: A number of basic problems in graph theory can be stated as packing problems. Let G1 and G2 be graphs of order at most n. We say that G1 and G2 pack if their vertex sets map injectively into {1,...,n} so that the images of the edge sets are disjoint. The concept of graph packing generalizes various extremal graph problems, including problems on fixed subgraphs (such as the Hamiltonian Cycle problem), forbidden subgraphs (Turan-type problems), and equitable coloring. The study of packings of graphs was started in the 1970s by Sauer and Spencer, and by Bollobas and Eldridge. Graph packing results have also been widely applied to the study of computational complexity of graph properties.We will discuss a few longstanding conjectures in this area, and present some recent results. In particular, we will present an extension (with A. Kostochka) of a classical theorem of Sauer and Spencer that is obtained through the characterization of its extremal graphs, and the best current result (with A. Kostochka and G. Yu) towards the well known Bollobas-Eldridge graph packing conjecture (1978), that further extends the Sauer-Spencer theorem.
