Extremal Problems on Graphs Related to Colorings and Cycle Structure

图G的顶点着色是将图G的顶点集划分成若干集合(称为色类)，使得G的每条边的两端都在不同的类中。基本的着色问题是找到这样一个具有最少颜色类别的划分。着色处理将一组对象划分为多个类以避免某些冲突的基本问题。该模型在时间表、调度、频率分配、排序等问题中有着广泛的应用。图着色理论是离散数学的中心课题之一。它涉及到组合学的其他重要领域，如Ramsey理论、图的子式、独立数、图的定向和图的填充。图的着色性质当然在很大程度上取决于这些图的圈结构。这个项目的目标是研究一系列与图和超图的着色有关的极值问题，其中答案取决于圈结构。该计划将在发展图和超图着色理论以及研究它们的圈结构方面取得重大进展。该项目涉及多名研究生和年轻研究人员。主要研究方向有：平均度小的色临界图、列表着色、不正确着色、均匀着色、独立数的界、超图着色、高色数图中指定长度的圈的存在性、图和超图中圈的Turan型问题、稠密图中多个不相交圈的存在性、填充和列表填充。这些方向的工作将利用并可能发展该领域的最新进展，包括研究人员和合作者的结果，特别是与他合作的研究生的结果。有希望的工具包括潜在语言和列表打包的概念。在期望的结果中，增强了关于不相交圈和具有顶点度限制的图中的最长圈的经典结果。

A coloring of vertices of a graph G is a partition of the vertex set of G into sets (called color classes) such that the ends of every edge of G are in different classes. The basic coloring problem is to find such a partition with the fewest color classes. 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 coloring is among central topics in discrete mathematics. It relates to other important areas of combinatorics, such as Ramsey theory, graph minors, independence number, orientations of graphs, and packing of graphs. Coloring properties of graphs certainly heavily depend on the cycle structure of these graphs. The goal of this project is to study a series of extremal problems related to colorings of graphs and hypergraphs, where answers depend on the cycle structure. The plan is to make significant advances in developing the theory of graph and hypergraph coloring and studying their cycle structure. The project involves a number of graduate students and young researchers. The main directions of study are planned to be color-critical graphs with small average degree, list coloring, improper colorings, equitable coloring, bounds on the independence number, hypergraph coloring, existence of cycles of specified length in graphs with high chromatic number, Turan-type problems on cycles in graphs and hypergraphs, existence of many disjoint cycles in dense graphs, packing, and list packing. Work in these directions will exploit and possibly develop recent advances in the field including the results of the investigator and collaborators, in particular, graduate students working with him. Among promising tools are the language of potentials and the notion of list packing. Among expected results are enhancements of classical results on disjoint cycles and on the longest cycles in graphs with restrictions on the vertex degrees.