RUI: Graph Coloring Parameters: Their Interplay with Number Theory Problems and Applications to Broadcast Communications

我们（PI和合作者）调查了两个主要主题。第一部分是关于距离图的分数和圆着色及其与两个数论问题的密切联系，即缺失差整序列的密度和“孤流子猜想”所涉及的参数。我们运用这些联系来加强对着色问题和数论问题的研究。此外，我们研究了Kneser图的圆形色数，重点研究了约简的Kneser图。第二个主要主题是由信道分配问题引起的。我们研究了距离标注，通过使用圆形距离标注作为有效的工具，我们将研究扩展到多级距离标注（或“无线电标注”），以获得更广泛的实际应用。一个多世纪以来，图的着色问题一直吸引着研究者。这部分是由于各种着色参数之间的迷人联系以及与其他领域问题的联系，部分是由于它们丰富的实际应用。PI和她的合作者研究了几个图着色问题，包括分数着色、圆形着色和由通道分配问题引起的着色。分数着色和圆形着色都可以看作是传统顶点着色的推广，在过去的二十年里得到了广泛的研究。研究这些着色参数与数论问题之间的联系，不仅提供了新的认识，而且促进了这一领域的知识发展。同样，对信道分配变化的研究为实际应用提供了模型，拓宽了目前对各种距离标记（着色）的研究。该项目的主要合作伙伴是台湾国立中山大学的朱旭定。

We (the PI and collaborators) investigate two major topics. The first is about fractional and circular coloring for distance graphs and their close connections to two number theory problems, namely, the density of integral sequences with missing differences and the parameter involved in the "lonely runner conjecture". We apply these connections to enhance the study of both coloring problems and problems in number theory. In addition, we investigate the circular chromatic number for Kneser graphs, with an emphasis on the reduced Kneser graphs. The second major topic is motivated by the channel assignment problem. We study distance two labeling, by using circular distance two labeling as an effective tool, and we extend the study to multi-level distance labeling (or "radio labeling"), for broader practical applications. Graph coloring problems have attracted researchers for more than a century. This is partially due to fascinating connections among various coloring parameters and connections to problems in other fields, and partially due to their abundant practical applications. The PI and her collaborators investigate several graph coloring problems including fractional coloring, circular coloring, and colorings motivated by the channel assignment problem. Both fractional coloring and circular coloring can be regarded as generalizations of the conventional vertex coloring, and have been studied extensively in the past two decades. Research on connections among these coloring parameters and problems in number theory not only provides new insight into, but also advances the knowledge in these fields. Likewise, research on variations of the channel assignment provides models to practical applications, and broadens the current study on various types of distance labeling (coloring). A major collaborator to the project is Xuding Zhu, National Sun Yet-Sen University, Taiwan.