随着通讯技术的高速发展以及各类应用需求的不断增加,下一代无线通讯网络的设计目标是以低成本高效率方式实现网络广覆盖和数据传输高速率。频谱资源是无线通讯网络的稀缺资源,如何有效充分地利用稀缺频谱资源是一个重要的研究课题。图论是离散数学和运筹学的重要组成部分,是近代应用数学的重要分支。图的染色问题是图论中研究的主要问题之一,有着很好的理论价值和实际意义。染色理论与分配问题密切相关,是解决通讯领域中频率分配问题(也被称为信道分配问题)的有力工具。论文介绍了染色的基本概念,引入Set染色、Set T染色、关联染色、邻点可区别边染色和邻点可区别均匀边染色理论,并基于这些染色理论研究了无线网络信道资源分配问题。本文的主要研究工作及创新点如下：(1)射频识别即RFID技术作为自动识别技术的一个重要分支,近年来得到了非常快速的发展,被视为构建物联网的基础和关键技术,并被应用到多个领域如供应链管理和智能交通等。当多个读写器同时工作于同一区域时可以有效地提高系统的读写速率和正确率,然而多读写器环境下会造成读写器对读写器的干扰和读写器对标签的冲突,严重影响系统的性能。本文利用多重图建立RFID干扰模型,并利用Set染色和Set T染色理论分配不同频率以避免读写器对读写器的干扰：同时分配不同时隙以避免读写器对标签的冲突。通过该方法为RFID读写器分配较少的频率和时隙资源,有效地避免多读写器之间的冲突,提高RFID系统的性能。(2)在无线通信网络中,多跳中继技术能够以低成本提供更广泛的信号覆盖,提高小区边缘用户服务质量。多跳传输网络必须分配额外的资源给中继链路,因此合理地设计中继资源分配方案对提升系统的资源利用效率具有重要的研究价值。本文针对正交频分多址(OFDMA)多跳中继蜂窝网络,提出一种基于染色理论的频率分配框架。该框架将多链路频率资源分配问题转化为关联染色问题；针对引入中继后的蜂窝系统,设计了一种新型的小区蜂窝结构,并基于关联染色理论对该结构提出了有效的频率分配方案。仿真结果及分析显示提出的频率方案有效的降低小区间的干扰,提高了频谱效率和系统性能。(3)随着全球信息化和无线网络的发展,农村无线通讯网络是农村信息化和实现可持续发展的关键技术。无线Mesh网络成本低廉,易架设,组织形式灵活,可扩展性强,将成为农村信息化建设的一种有效解决方案。本文针对农村Mesh网络,提出一种基于染色理论的信道分配框架。该框架利用邻点可区别边染色理论建立了相邻链路间的干扰模型,并通过分配不同的信道实现了同一节点处的相邻链路互不干扰的同步发送或接收数据；同时实现了相邻节点之间的双向链路互不干扰的同时发送和接收数据。该框架能够为农村Mesh网络分配较少信道资源,保证网络中各链路相互干扰最小,提高链路的利用率。此外,基于邻点可区别均匀边染色理论设计了新的信道分配框架,该框架利用邻点可区别均匀边染色理论协同优化整个网络,提高了信道资源的利用效率,实现了网络信道资源的均衡分配。本文通过笛卡尔积图和联图的邻点可区别均匀边染色理论研究表明,该信道分配框架在IEEE802.11a标准下实施是可行有效的。