无三角形平面图的邻和可区别全染色

摘要

设φ：v(G)∪E(G)→{1，2，…，k}为图G的一个正常k-全染色，即相邻的或者相关联的两个元素染不同的颜色．设φ为图G的正常k-全染色，即f(v)=∑φ(e)+φ（v），若对于图G的任意一条边uv∈E(G)都有f(u)≠f(v)，则称φ为图G的邻和可区别k-全染色，使得图G存在邻和可区别k-全染色的最小整数k称为图G的邻和可区别全色数，记作x"∑(G)． 本文主要考虑无三角形平面图及有最大度点限制的无三角形平面图的邻和可区别全染色．通过运用欧拉公式，权转移规则及组合零点定理，得到以下主要结论： (←) 结论1若图G为无三角形平面图且△(G)≥8，则有x"∑(G)≤△(G)+2． 结论2若图G为不含相邻最大度点的无三角形平面图且△(G)≥9，则有x"∑(G)=△(G)+1． 推论1设图G是无三角形平面图且△(G)≥9，若图G不含相邻最大度点，则x"∑(G)=△(G)+1，否则，x"∑(G)=△(G)+2．

目录

声明

符号说明

第一章 绪论

1.1基本定义与符号

1.2相关概念和研究进展

1.2.3 邻和可区别全染色、邻和可区别全可选择性

1.3本文主要结果

1.4证明用到的引理

第二章 无三角形平面图的邻和可区别全染色

第三章 不含相邻最大度点的无三角形平面图的邻和可区别全色数

参考文献

攻读硕士学位期间完成论文情况

致谢