Galvin 9700796 This award provides funds for an investigation into list coloring problems and other problems in combinatorics. List coloring problems in graph theory involve coloring the elements (vertices or edges) of a graph in such a way that adjacent or incident elements receive different colors, and the color of each element must be chosen from a prescribed list of colors associated with that element. For example, the list chromatic index (or list edge-chromatic number) of a graph is the least number n such that, given an arbitrary assignment of a list of n colors to each edge, there is a proper edge-coloring in which each edge is colored with a color from its list. The list (vertex-) chromatic number and list total chromatic number are defined analogously. The list coloring conjecture, due to Vizing, asserts that the list chromatic index of any graph (or multigraph) is equal to its (ordinary) chromatic index. The list coloring conjecture (LCC for short) is a notoriously deep and difficult problem. One of the major recent advances in this area was the PI's proof of the LCC for bipartite multigraphs, a result which included, as a special case, the well-known Dinitz conjecture about partial Latin squares. In this project, the PI hopes to make further progress on the LCC, by extending and applying his result on the bipartite case, and by other means. While the main focus of this project is on list colorings, the PI plans to investigate various other problems in combinatorics and graph theory, possibly including, but not limited to, the areas of Ramsey theory for paths, hypergraph games, cliques in factorizations of graphs and hypergraphs, and Frankl's conjecture on union-closed families. This research is in the area of combinatorics. Combinatorics is generally applicable to various practical problems: routing, scheduling, and other management science problems, communications, cryptology, etc. The mathematical formulation of a scheduling problem is a graph coloring problem. List coloring theory, besides being directly applicable to certain kinds of scheduling problems, is a useful tool in the study of classical graph coloring problems. The educational significance of a lot of work in combinatorics and graph theory, in particular the kind of work planned for this project, is that the problems and results, and even the methods used, are often accessible to bright undergraduate and high school students, so that they can enjoy the excitement of direct contact with current research.
