关于几类图的邻点可区别关联色数的研究

摘要

设图G是阶至少为2的连通图,设σ:I(G)→C为图G的k-关联着色,若
　　Qu={(u,uu′)｜u′∈N(u)}∪{((u′,u′u)｜u′∈N(u)},
　　若对任意uv∈E(G)满足Cu≠Cv,则称σ为G的k-邻点可区别关联着色,并称χai(G)=min{k｜存在G的k-邻点可区别关联着色}为G的邻点可区别关联色数.
　　本文对图论中几大图类的邻点可区别关联色数进行了研究及证明.
　　在第二章中,研究了几类特殊图的邻点可区别关联色数,包括风车图、Dm,4,Dm,n和齿轮图.
　　在第三章中,研究了路,圈C3m,C4m与完全图的广义Mycielski图的邻点可区别关联色数,拓展了图着色的领域,便于更好的研究图的结构.
　　在第四章中,首先给出倍图及m-倍图的定义,随后研究了路与完全图的倍图及m-倍图的邻点可区别关联色数.
　　论文的第五章主要研究了笛卡尔积图的邻点可区别关联色数,主要包括路与路的笛卡尔积图和路与完全图的笛卡尔积图的邻点可区别关联色数.

目录

封面

声明

中文摘要

英文摘要

目录

CONTENTS

1 绪 论

1.1 问题的提出

1.2 基本符号和术语

1.3 论文的主要研究内容与安排

2 几类特殊图的邻点可区别关联色数

2.1 研究背景及基本定理

2.2 主要结果及其证明

3. 图的广义Mycielski图的邻点可区别关联色数

3.1 广义Mycielski图的定义

3.2 主要结果及其证明

4 m-倍图的邻点可区别关联色数

4.1预备知识

4.2 图的倍图的主要定理

4.3 图的m-倍图的主要定理

5.两类图的笛卡尔积图的邻点可区别关联色数

5.1笛卡尔积图的基本概念

5.2 主要结果及其证明

6 结束语

致谢

参考文献

攻读硕士期间的研究成果