| 【中文题名】 | 图的全染色、（邻）点可区别全染色及分数染色 |
| 【英文题名】 | The Total Coloring, the (Adjacent) Vertex-distinguish Total Coloring and the Fractional Coloring of Graphs |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-8-8 |
| 【中关键词】 | 全染色,（邻）点可区别全染色,分数染色,Mycielski图,乘积图,Kneser图 |
| 【英关键词】 | the total coloring,the （adjacent）vertex-distinguishing,the fractional coloring,Mycielski graphs,the Cartesian product graphs,Kneser graphs,G_（a,b） graph,m-fold coloring,the fractional total coloring number, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 染色问题及许多图理论都是源自四色问题的研究。另外染色问题在组合分析和实际生活中有着广泛的应用,是图论研究中一个很活跃的课题,各类染色问题被相继提出并加以发展、应用。
图G的一个(正常)k-染色是将k种染色分配给G的顶点集V(G),使得相邻两顶点的颜色不同。定义色数为:χ(G)=min{k|图G有k-染色}。类似的,图G的一个(正常)k-边染色是将k种染色分配给G的边集E(G),使得有公共端点的两边的颜色不同。边色数χ′(G)=min{k|图G有k-边染色}。
全染色的概念是对点染色和边染色的推广,图的所有元素(顶点和边)都将染色且任相邻或关联的元素染色不同。全染色是图论染色的一个传统问题,由Vizing(1964)[23]和Behzad(1965)[24,25]各自独立提出的,同时分别给出全染色猜想。点可区别全染色和邻点可区别全染色[2]是染色问题的新生点,近来由张忠辅提出并给出了相应的两个猜想。
定义 设G(V,E)为图,k为正整数,S为k-色集,令映射f:V(G)∪E(G)→S。如果
(1)对任意uv,vw∈E(G),u≠w,有f(uv)≠f(vw)
(2)对任意uv∈E(G... |
| 【论文题纲】 |
|
中文摘要 |
5-12 |
|
英文摘要 |
12-20 |
|
第一章 引言 |
20-26 |
|
§1.1 全染色和(邻)点可区别全染色 |
21-23 |
|
§1.2 分数染色和分数全染色 |
23-26 |
|
第二章 图的全染色和(邻)点可区别全染色 |
26-38 |
|
§2.1 Mycielski图的全染色和(邻)点可区别全染色 |
26-29 |
|
§2.2 乘积图的邻点可区别全染色 |
29-32 |
|
§2.3 特殊图的全染色和邻点可区别全染色 |
32-38 |
|
第三章 分数染色 |
38-46 |
|
§3.1 Kneser图、G_(a，b)图的m-层染色 |
38-40 |
|
§3.2 乘积图的分数染色 |
40-42 |
|
§3.3 特殊图的分数全色数 |
42-46 |
|
附录 |
46-47 |
|
参考文献 |
47-51 |
|
在学期间发表的学术论文 |
51-52 |
|
致谢 |
52 |
|
| 【DOI】 | LunWen.ID:2.2008.11638 |
