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

RUI：图形着色参数：它们与数论问题的相互作用以及广播通信的应用

• 批准号: 0302456
• 负责人: Daphne Liu
• 金额: $ 13.5万
• 依托单位: California State L A University Auxiliary Services Inc.
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-01 至 2007-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0302456&HistoricalAwards=false
• 关键词: RUI; Graph; Coloring; Parameters; Their

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.

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