大围长的平面图的邻和可区分顶点列表色数

摘要

设G是一个图，N是一个正整数集，f是从V(G)到N的一个映射.图G中每一个点v关于f的邻和定义为Sf(v)=∑u∈NG(v)f(u).若对G中任意相邻两点u，v，有Sf（u）≠Sf(v)，则称f是图G的一个邻和可区分的顶点列表标号.设L为图G的一个列表配置，如果对任意点v有f(v)∈L（v），就称f是一个L-标号.若对图G的任意一个k-列表配置L，G都有一个邻和可区分的L-标号f，则称图G是邻和可区分k-可选的.图G的邻和可区分的顶点列表色数定义为ηl(G)=min{k:G是邻和可区分k-可选的}.
　　图的邻和可区分的顶点标号和顶点列表标号由Grytczuk等[5]提出，受到不少学者关注.Brandt，Diemunsch和Jahanbekam[4]首先研究了大围长平面图的邻和可区分的顶点列表色数，他们证明了当平面图G的围长至少为5，6，7和26时，其邻和可区分的顶点列表色数分别最多为19，9，8和3.本论文全面改进了上述结果.证明了当平面图G的围长至少为5，6，7，21时，图G的邻和可区分的顶点列表色数ηl(G)至多为15，8，7，3.

目录

摘要

第一章 绪论

1．1 基本概念

1．2 邻和可区分的顶点列表色数的研究现状

1．3 本文的主要结果

第二章 k-临界图

2．1 k-临界图

第三章 主要结论

3．1 围长至少为5

3．2 围长至少为6

3．3 围长至少为7

3．4 围长至少为21

参考文献

攻读学位期间取得的研究成果

致谢

声明