Coloring-related problems for graphs and hypergraphs with degree restrictions

点击翻译按钮获取中文摘要

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.