Packings and contractions of graphs and hypergraphs

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Alexandr V. Kostochka Packings and contractions of graphs and hypergraphs The notions of packings and minors are basic in graph theory. An important instance of combinatorial packing problems is that of graph packing. Graphs of order n pack, if there exists an edge disjoint placement of all these graphs into the complete graph with n vertices. In terms of graph packing, one can generalize or make more natural some graph theory problems or concepts. Important examples of packing problems are problems on existence of a given subgraph, coloring problems, Turan-type problems, and Ramsey-type problems. Another basic notion is that of a minor. A graph H is a minor of a graph G if H can be obtained from G by a sequence of contractions of edges and deletions of edges and vertices. A number of problems and results in graph theory relate impossibility to pack some graphs with the existence of some minors in these graphs. Maybe, the most famous example is Hadwiger's Conjecture that every non-k-colorable graph has the complete graph with k+1 vertices as a minor. The examples above (and many more) show that it is helpful and potentially fruitful to study in terms of graph packings and contractions a number of rather general problems that are rich enough models for many important applications. Areas of application include scheduling, database access, assignment of computer registers, data clustering, computer-aided design of printed circuits, positional games, DNA sequencing, etc. The goal of this project is to explore a series of extremal problems on packings and minors of graphs and hypergraphs, with restrictions on degrees of their vertices. It is expected that the results will make an essential step in understanding of these problems. Some proofs can lead to efficient packing and contraction algorithms; negative results will impose limits on what can be accomplished. The particular packing problem of equitable coloring has many applications in scheduling, partitioning, and load balancing problems. A fair amount of the work will be done jointly with graduate students and recent graduates of the University of Illinois at Urbana-Champaign.