论文摘要
图的着色理论在图论中占有重要地位．本文研究图的条件着色和动态着色，条件着色和动态着色都是近几年引入并进行研究的．设k>0，r>0，k，r∈Z，图G的一个（k，r）-着色是一个映射c：V（G）（?）C（k） = {1, 2,..., k}，满足：（1）如果uv∈E（G），那么c（u）≠c（v），（2）对于任意v∈V（G），|c（N（v））|≥min{r，dG（v）}．可以正常（k，r）-着色的最小k称为G的条件色数，记为χr（G）．动态着色是条件着色当r=2时的特殊情况，记为χd（G）．χr（G）的计算是一个NP问题，到目前为止，它的最好的上界是χr（G）≤△2（G）+1．本文第一部分给出了由图G构造条件图Gr的算法，讨论了条件图的色数与原图的条件着色色数的关系，得到了条件着色色数两个更好的上界：（1）χr（G）≤r△+1，（2）χr（G）≤1+rδ’．第二部分通过定义一个算法给出了强导出图，并用颜色对换的思想来研究平面图动态着色的上界问题，最后给出了定理“若G是平面图，则χd（G）≤5”新的证明方法．
论文目录
相关论文文献
- [1].完全图上的尾达渗流方差的上界估计[J]. 中国科学:数学 2020(01)
- [2].漳平市上界村乡村产业发展SWOT分析[J]. 台湾农业探索 2020(02)
- [3].一般矩阵特征值的相对扰动上界[J]. 五邑大学学报(自然科学版) 2016(01)
- [4].具有相依结构离散时间模型破产概率的上界[J]. 经济数学 2016(01)
- [5].最简多元最小上界算法研究[J]. 电脑知识与技术 2009(18)
- [6].基于快速转发服务机制的端到端延时上界预测研究[J]. 信号处理 2009(09)
- [7].一类正弦级数的上界估计[J]. 宝鸡文理学院学报(自然科学版) 2008(04)
- [8].诗话上界诗化美学——浅析“音乐是上界的语言”[J]. 美与时代 2008(02)
- [9].一类有限制条件的子集簇的模的上界[J]. 铜仁学院学报 2017(06)
- [10].基于网络演算的6LoWPAN网络性能确定上界研究[J]. 电子质量 2016(08)
- [11].多天线认知网络自由度的上界及实现方法[J]. 信息技术 2015(09)
- [12].当“灶王爷”爱上“温和腐败”[J]. 杂文选刊(下旬版) 2009(10)
- [13].二项风险模型中破产概率上界的估计[J]. 宝鸡文理学院学报(自然科学版) 2012(04)
- [14].实系数多项式根模上界估计的注解[J]. 佳木斯大学学报(自然科学版) 2010(02)
- [15].一个寿命分布类矩母函数上界的研究[J]. 韩山师范学院学报 2008(06)
- [16].一类存取结构信息率的上界[J]. 电脑知识与技术 2019(03)
- [17].树的扩展能量的上界[J]. 山东师范大学学报(自然科学版) 2018(03)
- [18].一类偏微分算子谱的上界估计[J]. 甘肃联合大学学报(自然科学版) 2010(03)
- [19].回归时间局部熵的多重分形谱的上界估计[J]. 华侨大学学报(自然科学版) 2009(04)
- [20].一类系统谱的上界[J]. 苏州市职业大学学报 2019(03)
- [21].关于图能量上界的注释[J]. 青海师范大学学报(自然科学版) 2014(02)
- [22].某类系统离散谱的上界估计[J]. 宁波职业技术学院学报 2012(02)
- [23].光滑支持向量分类机的收敛上界研究[J]. 计算机应用 2009(08)
- [24].关于lnx的一个上界估计及应用[J]. 数学学习与研究 2014(01)
- [25].B样条曲线与其控制多边形的局部距离上界[J]. 计算机辅助设计与图形学学报 2011(05)
- [26].带连续变利率风险模型最终破产概率上界[J]. 经济数学 2015(01)
- [27].基于差分方程计算循环复杂度符号化上界[J]. 软件学报 2011(09)
- [28].边Ramsey数上界研究[J]. 重庆邮电大学学报(自然科学版) 2011(06)
- [29].不确定系统的上界自适应动态神经滑模控制[J]. 吉林大学学报(信息科学版) 2010(03)
- [30].推广的Ramsey数的上界估计[J]. 同济大学学报(自然科学版) 2009(01)