RUI: Graph Coloring and Choosability

California State L A University Auxiliary Services Inc., Los Angeles CA

Investigators

Abstract

Graph coloring problems have attracted researchers for more than a century. This is partially due to their abundant practical applications and their relations to other fields. For instance, the well-known Four Color Theorem asserts that four colors is always enough to color the regions of a given map such that each region gets one color and two regions sharing some border must receive different colors. This RUI project focuses on intensive research on several graph coloring and choosability problems, which have been frequently used as models for practical applications such as scheduling, traffic control, and the channel assignment problems. For instance, in scheduling final exam times of all courses at a college, we construct a graph model by representing each course by a vertex, and connecting two vertices (courses) by an edge if a student is taking both courses. The chromatic number of such a graph model provides the minimum number of exam time periods needed in order to schedule all final exams without conflict. In addition, if some courses set restrictions on certain dates and times, then it becomes a graph choosability problem. Research suitable for undergraduates will be incorporated into Graph Theory and Graduate Seminar courses, providing non-traditional and underrepresented students opportunities to learn cutting edge research methods, and will involve three graduate students yearly to work on research projects. Graphs provide excellent models for various problems motivated by the channel assignment problem, in which we assign channels to cities or stations such that interference is avoided and the span of channels used is minimized. This RUI project focuses on intensive research on graph coloring and choosability topics with emphasis on utilizing research methodologies and results in number theory, topology, and algebra. The goal is to bring new insight into, and broaden the study of, areas of graph theory that are related to number theory, topology, and algebra, as well as applications to broadcast communication. Specifically, the PI will investigate distance graphs and number theory problems, topological combinatorics, graph choosability, and colorings motivated by the channel assignment problem.