Extremal Problems on Graphs Related to Colorings and Cycle Structure

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

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.