论文部分内容阅读
本报告包含了我在中国科学院数学与系统科学研究院系统所做博士后期间(2002.8-2004.8)所做的工作,其中主要有无三角形图的可选择性,点色数与列表点色数相等图的性质以及唯一列表染色图等几方面内容。 已知Gr(o)tzsch图是最小的无三角形的四色图,并且阶数不超过13的所有二部图都是三可选的.在第二章,我们证明了所有阶数不超过10的无三角形的非二部图都是三可选的,从而证明了Gr(o)tzsch图是最小阶数的满足xl(G)=4的无三角形图。 一个图的色数小于或等于其列表色数.Ohba证明了任给一个图G,都存在正整数n0,只要n大于n0,就有图G∨Kn满足列表色数与色数相等.我们用φ(G)来表示最小的n使得图G∨Kn满足列表色数与色数相等.Enomoto等人猜测对完全k部图K(m,m,…,m)及任意m≥2、k≥1有φ(G)=(m-2)(k-1),在第三章,我们证明了Enomoto猜想对于m=3的情形成立。 给定一个n阶图G,我们用f(G)来表示最小的整数k使得图G∨ Ek后不再是n可选的.Gravier等人猜测对于无三角形的图G,有f(G)=(n2)μ(G)nn-2μ(G),这里n是图G的阶数,μ(G)是图G的最大匹配数.在第四章里,我们证明了该猜想对于森林是正确的,并且提出了几个相应的公开问题。 在第五章,我们否定了一个关于极大唯一列表染色的猜想.Akbari等人猜测一个极大唯一f列表可染图一定是f可选的,我们给出了一个简单的反例。