Coloring-related problems for graphs and hypergraphs with degree restrictions

具有度数限制的图和超图的着色相关问题

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

A (proper) coloring of vertices of a graph or hypergraph G is a partition of the vertex set of G into sets (called color classes) such that no edge of G is fully contained in any of the classes. The basic coloring problem is to find such a partition with the fewest color classes. The aim of this project is to study extremal problems related to coloring of (hyper)graphs involving degrees of vertices, a number of whose arose during the work of the PI and co-PI with students at the University of Illinois. It is expected that the joint work and combinations of the ideas and approaches of the PI and the co-PI will allow to get the results that will make an essential step in understanding of these problems. Among important topics are color-critical graphs with small average degree, list colorings, improper colorings, coloring of graphs embedded into surfaces, equitable coloring, bounds on the independence number, and hypergraph coloring. Among promising tools is the language of potentials.Coloring deals with the fundamental problem of partitioning a set of objects into classes that avoid certain conflicts. This model has many applications, for example, in time tabling, scheduling, frequency assignment and sequencing problems. The theory of graph and hypergraph coloring has a central position in discrete mathematics. It relates to other important areas of combinatorics, such as Ramsey theory, graph minors, independence number of graphs and hypergraphs, orientations of graphs, and packing of graphs. The PI and the co-PI plan to make significant advances in developing the theory of coloring of sparse graphs and hypergraphs. They will involve into work a number of graduate students and very recent graduates of the University of Illinois. The research guidance and involvement of graduate students contributes to their professional development and reputation. The results will be published in leading international journals in the field and presented at international scientific conferences. This will support the reputation of the University of Illinois. The results will be used in graduate courses and discussed at research seminars at the University of Illinois.

一个图或超图G的顶点的（真）染色是将G的顶点集划分为若干个集合（称为色类），使得G的任何边都不完全包含在任何色类中。基本的着色问题是找到这样一个分区与最少的颜色类。该项目的目的是研究涉及顶点度的（超）图着色的极值问题，其中一些问题是在PI和co-PI与伊利诺伊大学学生的工作期间出现的。预计PI和co-PI的想法和方法的联合工作和组合将允许获得将在理解这些问题方面迈出重要一步的结果。重要的议题包括 小平均度的色临界图，列表着色，非正常着色，嵌入到曲面中的图的着色，均匀着色，独立数的界，超图着色。着色处理的是将一组对象划分为避免某些冲突的类的基本问题。该模型在时间表、调度、频率分配和排序等问题中有着广泛的应用。图与超图着色理论在离散数学中占有核心地位。它涉及到组合数学的其他重要领域，如拉姆齐理论，图子式，图和超图的独立数，图的方向和图的包装。PI和co-PI计划在发展稀疏图和超图的着色理论方面取得重大进展。他们将涉及到工作的研究生和伊利诺伊大学的应届毕业生的数量。研究生的研究指导和参与有助于他们的专业发展和声誉。研究结果将发表在该领域的主要国际期刊上，并在国际科学会议上发表。这将有助于提高伊利诺伊大学的声誉。研究结果将用于伊利诺伊大学的研究生课程并在研究研讨会上进行讨论。