图的全染色、邻点可区别全染色及分数染色

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

染色问题是图论研究的经典领域，它源自四色定理的研究，是图论研究中一个很活跃的课题．另外染色问题在组合分析和实际生活中有着广泛的应用，因此各类染色问题被相继提出并加以发展、应用．图G的一个(正常)k-染色是将k种颜色分配给G的顶点集V(G)，使得相邻两顶点的颜色不同．定义色数为：x(G)=min{k|图G有k-染色)．类似地，图G的一个(正常)k-边染色是将k种颜色分配给G的边集E(G)，使得有公共端点的两边的颜色不同．边色数x’(G)=min{k}图G有k-边染色}．图的全染色的概念是对点染色和边染色的推广，是对图的所有元素(顶点和边)都进行染色，使得相邻或关联的两元素颜色不同．图的全色数xT(G)=min{k|图G有k-全染色}．全染色是图论染色的一个传统问题，由Vizing(1964)[1]和Behzad(1965)[2，3]各自独立提出的，同时分别给出全染色猜想．邻点可区别的全染色的概念是图的一正常的全染色且任相邻顶点的色集不同，由张忠辅[4]在全染色的基础上提出的，并同时给出了相应的猜想和两个引理．用xat(G)表示图G的邻点可区别的全色数．超图是—般图的一个重要推广，超图的染色问题也是图的染色问题的推广．1966年Behzad首次开始超图染色的研究，逐渐地将染色理论引入到超图中来．超图的全染色的概念是图的全染色概念的一个自然推广．王维凡，张克民在[5]中给出了超图全染色的概念，分为弱全染色和强全染色两种．超图H-(V. E)的弱(强)全染色是对超图的所有元素(顶点和超边)都将进行染色，使得顶点是弱(强)染色，边是强边染色，并且任意关联的顶点和超边的颜色不同．超图的弱(强)全色数XWT(H)=min{k超图H有弱k-全染色}(XST(H)=min{k|超图日有强k-全染色})．图的分数染色的概念是从图染色的分数推广的角度提出的． E．Scheinennan和D．Ullman在[6]中提出了分数染色的概念，并指出确定一个图的分数色数是NP-困难的．用xf(G)表示图G的分数色数．

著录项

作者
王颜妮;
展开▼
作者单位

山东师范大学;

展开▼
授予单位山东师范大学;
学科应用数学
授予学位硕士
导师姓名孙磊;
年度 2008
页码
总页数
原文格式 PDF
正文语种中文
中图分类图论;
关键词
图论; 染色问题; 邻点可区别; 分数染色;

相似文献

中文文献
外文文献
专利

1. 若干图的邻点可区别的I-全染色和邻点可区别的I-均匀全染色 [J] . 张婷 ,赵慧霞 ,杜佳 . 广州大学学报（自然科学版） . 2020,第001期
2. 立方图的邻点可区别全染色及一般邻点可区别全染色 [J] . 孟献青 . 内蒙古师范大学学报：自然科学汉文版 . 2015,第1期
3. Pn×Pm图的邻点可区别全染色和邻点强可区别全染色 [J] . 张锐 ,刘永平 ,刘海涛 . 甘肃高师学报 . 2007,第005期
4. 关于路的k-方图的邻点可区别-边全染色和第一类弱全染色 [J] . 严谦泰 . 安阳师范学院学报 . 2021,第002期
5. 两类Mycielski's图的邻强边染色和邻点可区别全染色 [J] . 戴韵 ,卜月华 . 浙江师范大学学报（自然科学版） . 2006,第001期
6. C<,m>·F<,n>的邻点可区别的边染色 [C] . 刘君 ,赵传成 ,任志国 . 中国运筹学会第七届学术交流会 . 2004
7. 图的全染色、（邻）点可区别全染色及分数染色 [A] . 孙艳丽 . 2006

图的全染色、邻点可区别全染色及分数染色

目录

摘要

著录项

相似文献

相关主题

期刊订阅