Packings and contractions of graphs and hypergraphs

图和超图的包装和收缩填充和子图的概念是图论中的基本概念。图布局问题是组合布局问题的一个重要实例。N阶图Pack，如果所有这些图都存在边不相交的放置到n个顶点的完全图中。在图填充方面，人们可以将一些图论问题或概念推广或变得更自然。布局问题的重要例子是关于给定子图的存在性问题、着色问题、Turan型问题和Ramsey型问题。另一个基本概念是未成年人。图H是图G的子图，如果H可以通过边的收缩和边和点的删除的序列从图G中得到。图论中的一些问题和结果涉及到一些图的不可包装与这些图中某些子项的存在有关。也许，最著名的例子是Hadwiger的猜想，即每个非k-可染图都有k+1个次点的完全图。上面的例子(以及更多的例子)表明，从图填充和收缩的角度研究一些相当一般的问题是有帮助的，而且可能是有成果的，这些问题的模型足够丰富，可以用于许多重要的应用。该项目的应用领域包括调度、数据库访问、计算机寄存器分配、数据聚类、印制电路的计算机辅助设计、位置博弈、DNA测序等。本项目的目标是探索一系列关于图和超图的包装和子式的极值问题，并对它们的顶点的度数进行限制。预计这些结果将在理解这些问题方面迈出重要的一步。一些证明可以导致高效的打包和收缩算法；否定的结果将限制所能完成的事情。均匀着色的特殊布局问题在调度、分区和负载平衡问题中有许多应用。相当多的工作将与伊利诺伊大学厄巴纳-香槟分校的研究生和应届毕业生共同完成。

Alexandr V. KostochkaPackings and contractions of graphs and hypergraphsThe 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.