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

点击翻译按钮获取中文摘要

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.