Collaborative research on degree conditions for packing and covering problems on graphs

点击翻译按钮获取中文摘要

Packing and covering are dual notions that are basic in combinatorial optimization and in combinatorics, in general. They are different and yet very closely related. One important instance of combinatorial packing problems is that of graph packing. Graphs of size n pack, if there exists an edge disjoint placement of all these graphs into the complete graph with n vertices. Various classical combinatorial problems can be modeled as packing or covering problems.For example, the problem of existence of a spanning cycle in an n-vertex graph is the question whether the n-cycle packs with the complement of G. Important examples of packing and covering problems are problems on existence of a given subgraph, coloring problems, Turan-type problems, domination problems and Ramsey-type problems. These examples (and many more) show that (hyper)graph packings and coverings are rather general problems and 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 main thrust of the project is to explore a series of extremal packing and covering problems for graphs and hypergraphs, with restrictions on degrees of their vertices. It is expected that the results will make an essential step in understanding extremal packing and covering problems for graphs and hypergraphs.Some proofs can lead to efficient packing and covering 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. It will be studied also from an algorithmic viewpoint. A fair amount of the work will be done jointly with graduate students and recent graduates of the University of Illinois at Urbana-Champaign.