图的邻和可区别边染色和邻和可区别全染色

摘要

对于图G(V,E)，给定一个正整数k，一个正常k边染色是一个映射c：E→{1.2……k}，对于任意两条相互关联的边e1,e2∈(G),有c(e1)≠c(e2)。一个正常k全染色是一个映射c:V∪E→{1.2……k}，使得每一对相邻的点和相邻的边以及相关联的点和边所对应的值不一样。设c是G的一个正常边染色，对V（G）中任意一点ν，令∑c（ν）代表与v相关联的边的颜色之和，如果对E(G)中的每条边uν，有∑c(u)≠∑c(ν)，那么这样一个正常边染色叫做邻和可区别边染色，满足这种染色的最小k值叫做邻和可区别边色数，用χ'∑(G)来表示。类似地对于图G(V,E)的正常全染色，对于V(G)中任意一点v，令∑s(ν)代表与v相关联的边的颜色与点v的颜色之和。如果对E(G)中的每条边uν，有∑s(u)≠∑s(ν)，那么这样一个正常全染色叫做邻和可区别全染色。满足这种染色的最小k值叫做邻和可区别全色数，用χ'∑(G)来表示。
　　本文主要证明了两个定理，第一个定理，对于不含孤立边的简单图G，如果mad(G)<10/3，那么χ'∑≤k，其中，k=max{Δ+2,14}。第二个定理，对于平面图G，如果Δ(G)≥5且g(G)≥5，那么χ'∑(G)≤Δ(G)+3。
　　本文主要内容具体分为四章展开：
　　第一章，介绍研究领域的相关背景及本文用到的基本概念和研究现状。
　　第二章，利用欧拉公式及权转移规方法证明了第一个定理。
　　第三章，利用权转移法规则构造反例证明了第二个定理。
　　第四章，对本文的结果进行了简单的总结并作了进一步的展望。

目录

声明

致谢

变量注释表

1 绪论

1.1 研究背景（Research Background）

1.2 基本概念（Basic Definitions)

1.3 研究现状（Research Status)

2 最大平均度小于10/3的邻和可区别边染色

2.1 相关定理及引理（Related Theorem And Lemma）

2.2 极小反例的性质（Property Of Minimal Counterexample）

2.3 权转移规则（Discharging Process）

3 围长不小于5的邻和可区别全染色

3.1 极小反例的结构（Structure Of Minimal Counterexample）

3.2 权转移规则（Discharging Process）

4 总结与展望

参考文献

附录

作者简历

学位论文数据集