Packing Problems for Graphs and Hypergraphs

An important instance of combinatorial packing problems is that of graph packing. Two graphs G_1 and G_2 “pack” if G_1 is a subgraph of the complement of G_2; or, equivalently, if G_2 is a subgraph of the complement of G_1. Many problems and concepts of graph theory can be expressed in a unified (and sometimes more natural) form using the language of graph packing.

As an example, the existence of a hamiltonian cycle in an n-vertex graph (a close relative of the Traveling Salesman Problem) is equivalent to the question whether the n-cycle Cn packs with the complement G_ of G. As another example, a graph is k-colorable if and only if G packs with a graph that is the union of k cliques. Many timetabling, sequencing, and scheduling problems can be stated naturally as packing problems.

Over the past three years Professor Kostochka has encountered some interesting packing problems for graphs and hypergraphs. During his Center appointment he will study several extremal problems on packing of (hyper)graphs involving degrees of vertices. In particular he will work on Ore-type packing problems and H-linked graphs (topics introduced jointly with his student G. Yu). Other areas he will pursue include coloring uniform hypergraphs with few edges (jointly with his student M. Kumbhat and with V. Rödl) and equitable coloring.

Professor Kostochka will also participate in a semester-long program, “Combinatorics: Methods and Applications in Mathematics and Computer Science,” sponsored by the Institute for Pure and Applied Mathematics at the University of California at Los Angeles. This will be a unique opportunity to work with collaborators in a creative environment on basic problems, speeding up and enhancing his research. He plans to incorporate his results into graduate courses and research seminars taught at the University of Illinois Mathematics Department. Some of the work will also form parts of participating students’ Ph.D. dissertations.