POWRE: Distance Graphs and Channel Assignment Problems

该项目开启了距离图和通道分配（也称为t -着色）领域的进一步研究。这两个领域多年来一直是活跃的研究领域。这个项目有两个主要组成部分。第一部分扩展了距离图和t -着色及其联系问题的研究。由PI[1997]证明了距离图与t -着色之间的第一个联系，并用于得到Eggleton， Erdos和Skilton[1985]提出和研究的距离图问题的可拓解。Chang和Zhu[1997]的联合工作彻底解决了这个问题，并证明了第二个联系，表明距离图的分数色数等于它的渐近着色比。Griggs和PI[1996]表明，后一个参数与早期的一个数论问题密切相关，即Cantor和Gordon[1975]和Haralambis[1977]研究的缺失差异序列的密度问题。本项目将沿着这一研究方向探索距离图与t -着色之间的其他有用联系，进一步得到距离图的色数、圆色数和分数色数的结果，并研究feggleton、Erdos和Skilton问题的推广。从信道分配问题的实际情况出发，研究了几种不同的t -着色方法。本课题的第二部分将在PI过去和现在工作的基础上进行延伸研究，并共同研究t -着色的两种变体，即图的无孔t -着色和距离二标注。对距离标注的研究也有利于实际的两级干扰信道分配问题。有关该项目的最新参考文献和作品，欢迎读者访问PI的网站：www.calstatela.edu/faculty/dliu/dliu.htm或电子邮件：dliu@calstatela.edu.This power项目由MPS多学科活动办公室（OMA）支持。

This project initiates further research on the fields of distancegraphs and the channel assignment (also named T-coloring). Bothfields have been active research areas for years.There are two major components in this project. The first oneextends research on problems on distance graphs and T-coloringand their connections. The first connection between distancegraphs and T-coloring was proved by the PI [1997] and was used toobtain extend solutions on a problem on distance graphs raisedand studied by Eggleton, Erdos and Skilton [1985]. A joint workwith Chang and Zhu [1997] completely solved the problem andproved the second connection which showed that the fractionalchromatic number of a distance graph is equal to its asymptoticT-coloring ratio. The latter parameter was shown, by Griggs andthe PI [1996], to be closely related to an earlier number theoryproblem, namely, density of sequences with missing differences,studied by Cantor and Gordon [1975] and by Haralambis [1977]. Theproject will follow this direction of research to explore otheruseful connections between distance graphs and T-coloring, toobtain further results on distance graphs including theirchromatic number, circular chromatic number and fractionalchromatic number, and to study a generalization of the problem ofEggleton, Erdos and Skilton.Motivated from practical situations in the channel assignmentproblem, several variations of T-coloring have been studied. Thesecond part of this project will extend the research of the PI'spast and current work and joint work on two variations ofT-coloring, namely, no-hole T-coloring and distance two labelingsof graphs. Research on the distance two labelings will alsobenefit the practical two-level-interference channel assignmentproblem.For update references and works of this project, readers arewelcome to visit the PI's web site at:www.calstatela.edu/faculty/dliu/dliu.htm or email to:dliu@calstatela.edu.This POWRE project is supported by the MPS Office of Multidisciplinary Activities (OMA).