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.
The abstract of the project said: ``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.'' The work followed the proposals outlines and a number of strong results were obtained. Among most important results are (1) A proof of Gallai's Conjecture from 1963 (exactly 50-year-old) on the minimum number of edges in k-critical n-vertex graphs, (2) A refinement of Corradi-Hajnal Theorem from 1963 (also exactly 50-year-old) on disjoint cycles in graphs with given minimum degree, (3) Resolving a problem by Borodin from 1974 on description of non-k-colorable almost k-degenerate graphs, (4) Resolving a problem by Kurek and Rucincki from 1994 on sparse non-(1,1)-colorable graphs, (5) Extending the Bollobas-Eldridge Theorem from 1978 on packing of graphs to the hypergraph setting. Some new methods and techniques were invented to prove the grant results. These results make an essential step in understanding of the problems considered in the grant. Some proofs lead to efficient packing and contraction algorithms. Negative results impose limits on what can be accomplished. The results of the grant were written in about 40 scientific papers submitted to leading journals and conference proceedings (more than 20 of them are already published). They were reported in talks at about 25 international and AMS conferences and also at seminars and colloquiua in the US and abroad. A fair amount of the work was done jointly with graduate students and recent graduates of the University of Illinois at Urbana-Champaign. At least 9 students were significantly involved. In particular, results (1) and (4) above are joint with student M. Yancey, result (2) is joint with student E. Yeager, result (5) is joint with student C. Stocker. For several students the results are/will be a substantial part of their Ph. D. Theses. The results of the grant are and will be used in graduate courses at the University of Illinois.
