关于图的几类着色和与强度的研究

论文摘要

图G的最优着色是从顶点集V到颜色集C的一个映射f:V→C,使得G中任意两个相邻的顶点均有不同的象,而且（?）f（v）取得最小值,称min（?）f（v）为G的最小顶点着色和（MVCS）,记为∑（G）,即∑（G）=min（?）f（v）.如果f是G的一最优着色,则将f所需要的最小颜色数称为G的顶点强度,记为s（G）.对于一般的图类,s（G）不小于x（G）.本文第二章研究了路、圈、星、轮、扇、完全二部图、次完全二部图的∑（G）与s（G）,给出了乘积图Cm×Pn、六角系统、花图、Cm·Fn图和一类幂图Pnk的s（G）.图G的最优边着色是从边集E到颜色集C的一个映射f:E→C,使得G中任意两个相邻的边均有不同的象,而且（?）f（e）取得最小值,称min（?）f（e）为G的最小边着色和（MECS）,记为∑’（G）,即∑’（G）=min（?）f（e）.如果f是G的一最优边着色,则将f所需要的最小颜色数称为G的边强度,记为s’（G）.目前关于∑’（G）与s’（G）的研究还不多.在第四章中,研究了次完全二部图的∑’（G）与s’（G）.在图的全着色的基础上,对以上两个概念加以推广,本文在第三章中给出了图的最优全着色与强度的定义.对图G=（V,E）的映射f:{V,E}→{1,2,…,k},若满足下列条件:（1）（?）u,v∈V,uv∈E,且u≠v,有f（u）≠f（v）;（2）（?）uv,uw∈E,v≠w,有f（uv）≠f（uw）;（3）（?）u,V∈V,uv∈E,且u≠v,有f（u）≠f（uv）,f（v）≠f（uv）,则称f为G的一个k-全着色.若f为G的一个全着色,称∑"（G）=min（?）（f（v）+f（e））为G的最小全着色和（MTCS）,将f所需要的最小颜色数称为G的强度,记为sT（G）.在第三章中,利用穷染法和换色技巧得到了几类图的∑"（G）与sT（G）.

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 图论的基本知识
• 1.2 问题的提出和已有的一些结论
• 1.3 本文的主要结果和内容安排
• 2 若干图类的着色和与顶点强度
• 2.1 基本概念
• 2.2 主要结果
• 3 图的全着色和与强度
• 3.1 基本概念
• 3.2 主要结果
• 4 次完全二部图的边着色和与边强度
• 4.1 基本概念
• 4.2 主要结果
• 5 结束语
• 致谢
• 参考文献