RUI: Graph Coloring and Choosability

一个多世纪以来，图的着色问题一直吸引着研究者。这部分是由于它们丰富的实际应用及其与其他领域的联系。例如，众所周知的四色定理断言，四种颜色总是足以为给定地图的区域上色，这样每个区域获得一种颜色，共享某些边界的两个区域必须获得不同的颜色。该RUI项目侧重于对几个图形着色和可选择性问题的深入研究，这些问题经常被用作调度、交通控制和通道分配问题等实际应用的模型。例如，在安排一所大学所有课程的期末考试时间时，我们通过用一个顶点表示每门课程来构建一个图模型，如果学生同时选修这两门课程，则用一条边连接两个顶点（课程）。这种图模型的色数提供了为了安排所有期末考试而不发生冲突所需的最小考试时间段数。此外，如果某些课程对某些日期和时间设置了限制，那么它就变成了一个图形可选择性问题。适合本科生的研究将被纳入图论和研究生研讨会课程，为非传统和代表性不足的学生提供学习前沿研究方法的机会，并将每年有三名研究生参与研究项目。图表为各种由信道分配问题引起的问题提供了很好的模型，在这个问题中，我们将信道分配给城市或电台，这样就避免了干扰，并且使用的信道跨度最小。该RUI项目侧重于图形着色和可选择性主题的深入研究，重点是利用数论，拓扑学和代数的研究方法和成果。我们的目标是为与数论、拓扑和代数相关的图论领域以及广播通信的应用带来新的见解，并拓宽研究范围。具体来说，PI将研究距离图和数论问题、拓扑组合学、图的可选择性，以及由信道分配问题引起的着色。

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.