Problems Related to Graph Packing

Arizona State University, Scottsdale AZ

Investigators

Abstract

ABSTRACT Principal Investigator: Kierstead, Henry A. Proposal Number: DMS - 0901520 Institution: Arizona State University Title: Problems Related to Graph Packing This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). The theory of graph packing provides a general framework for organizing many areas of graph theory. Two famous results that can be phrased in this language are Dirac's Theorem on the existence of Hamiltonian cycles and the Hajnal-Szemerédi Theorem on equitable coloring. Both are special cases of another important graph packing problem known as Seymour's Conjecture. This conjecture has been proved for extremely large graphs by Komlós, Sárkõzy and Szemerédi using their own Blow-Up Lemma and Szemerédi's Regularity Lemma, but is still open for ordinary sized graphs. A final example is the Bollobás-Eldridge-Catalin Graph Packing Conjecture, for which only very special cases have been solved. Each of these problems requests a packing of certain graphs with bounded maximal degree. Many versions and special cases of these problems have been investigated by researches hoping to gain insight into the Graph Packing Conjecture, as well as other areas of graph theory. So far these efforts have met with only partial success. This project aims to advance these investigations, paying particular attention to variations in which the maximum degree condition is replaced by a weaker condition such as maximum Ore-degree, coloring number, or two coloring number. Graph theory is used to model many practical problems. This project addresses questions of the following form. Given a graph that satisfies some local density condition such as having large minimal degree, e.g., every employee in a company works well with 2/3 of the other employees, can we always find a sparse, but highly uniform, subgraph, e.g., a circular ordering of the employees so that every employee works well with each of the two preceding employees and each of the two succeeding employees? This example is essentially Pósa's Conjecture (1960). In the early years of graph theory many elementary techniques were introduced for answering such questions. One example is the proof of Dirac's Theorem (1950). However many natural questions remained unanswerable. Over the last thirty years deep and powerful techniques have been developed for attacking many of these questions, but generally they can only be applied to unrealistically large graphs. For example, Pósa's conjecture has only been proved for such enormous graphs. On the other hand, elementary, but complicated, methods can be used to show an open-ended (path) version of Pósa's Conjecture for all graphs. One of the challenges for this project is to prove the full Pósa Conjecture for all graphs.