Coloring-related problems for graphs and hypergraphs with degree restrictions

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

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.