图的无重复染色

摘要

本文研究了图的无重复列表染色数和图的途径无重复染色数，图的途径无重复分数染色数。给出了路的无(2+(ε))-重复列表染色数的上界，确定了路和圈的途径无重复染色数以及途径无重复分数染色数，改进了树的途径无重复染色数的上界。同时研究了图的无r-重复染色，其中r是一个实数，研究了路和圈的无3-重复分数染色数。
　　本文分为四章。第一章介绍无重复列表染色提出的背景及给出其定义，并对图的无r-重复染色，无r-重复列表染色，途径无重复染色和途径无重复分数染色数进行阐述。第二章分别用概率的方法和熵方法(entropymethod)给出了无(2+(ε))-重复列表染色数的上界。第三章主要讨论路和圈以及树的途径无重复染色数。第四章讨论无r-重复染色数。

目录

摘要

1 绪论

1．1 基本概念

1．2 图的无重复染色的研究概况

1．3 本文的主要结果

2 图的路无r-重复列表染色数的上界

2．1 概率方法

2．2 熵方法

3 图的途径无重复染色数

3．1 路

3．2 圈

3．3 树

4 图的无r-重复染色数

4．1 无3-重复分数染色数

4．2 πr(d)

参考文献

在学期间的研究成果及发表的论文

致谢

声明