POWRE: Distance Graphs and Channel Assignment Problems

该项目开启了距离图和通道分配(也称为T-着色)领域的进一步研究。这两个领域多年来一直是活跃的研究领域。这个项目有两个主要组成部分。第一章是对距离图和T-染色问题及其联系的研究。距离图与T-染色之间的第一个联系是由PI[1997]证明的，并被用来对Eggleton，Erdos和SKirton[1985]提出和研究的一个距离图问题得到推广解。张和朱[1997]的工作彻底解决了这个问题，并证明了距离图的分数色数等于它的渐近T-着色比的第二个联系。Griggs和Pi[1996]证明后一个参数与早期的数论问题密切相关，即由Cantor和Gordon[1975]和Haralambis[1977]研究的具有缺失差异的序列的密度。本项目将沿着这一研究方向，探索距离图与T-染色之间的其他有用的联系，得到距离图的进一步结果，包括它们的色数、圆色数和分数色数，并研究Eggleton，Erdos和Skylton问题的推广。本课题的第二部分将对图的两种变种，即图的无孔T-染色和距离二标号的PI过去和当前工作及其联合工作进行进一步的研究。对两个标号距离的研究也将有助于实际的两级干扰通道分配问题。有关本项目的最新参考资料和作品，欢迎读者访问PI的网站：www.calstatela.edu/intachary/dliu/dliu.htm或发送电子邮件至dliu@calstatela.edu.本POWRE项目由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).