Packings and contractions of graphs and hypergraphs

图和超图的打包和收缩

• 批准号: 0965587
• 负责人: Alexandr Kostochka
• 金额: $ 27万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-06-01 至 2013-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0965587&HistoricalAwards=false
• 关键词: Packings; contractions; graphs; hypergraphs

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.

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