论文部分内容阅读
图G的一个正常顶点染色是指k种颜色1,2,…,k对于G的各顶点的一个分配,使得任意两个相邻的顶点分配以不同颜色。若图G有一个正常k-点染色,那么就称图G是k-点可染色的。图G的色数是指G有一个正常后顶点染色的数k的最小值,用χ(G)表示。
图G的一个顶点色列表L是一个颜色集合簇,它指定G的每个顶点υ一个颜色集合L(υ).若G有一个正常的顶点染色π,使得对每一个顶点υ∈ V,有π(υ) ∈L(υ),则称G为L-顶点可染的或者称π是G的一个L-染色。若对每一个满足|L(υ)|≥k,υ∈ V的L,G都是L-点可染的,则称G是k-点可选择的,简称G是k-可选择的。G的顶点列表色数是使得G是k-可选择的最小的非负整数后。
假若染色π是图G的正常顶点染色,并且对于G中的任何一个圈子图C都应用至少3种颜色,那么我们称染色π是G的一个无圈染色。图G的无圈色数χa(G)就是使得G是无圈k-可染的最小的非负整数k。若G有一个正常的无圈染色π,使得对每一个顶点υ∈ V,都有π(υ)∈ L (υ),则称G是无圈L-可染的或者称π是G的一个无圈L-染色。若对满足|L(υ)|≥k,υ∈ V的色列表L,G都是无圈L-可染的,那么称G是无圈k-可选择的。G的无圈列表色数χ<,a>(G)是使得G是无圈k-可选择的最小的非负整数k。
1976年,对于平面图的正常顶点着色,Steinberg提出猜想:每个不包含4-圈和5-圈的平面图是3-可染色的。
2002年,Borodin等人首次研究了平面图的无圈L-染色问题,并且在文献[2]中证明了每个平面图都是无圈7-可选择的。与此同时,他们还在此文献中提出了一个更具有挑战性的猜想:每个平面图都是无圈5-可选择的。
本学位论文主要围绕这两个猜想,对一些平面图类展开研究。
在第一章中,给出本文所用到的基本概念,简述了相关领域的研究现状以及呈现了本文的主要结果。
在第二章中,证明了以下两个结果:
(1).每个不包含{4,6,7,9}-圈的平面图是3-可染色的;
(2).每个不包含{4,6,8}-圈的平面图是3-可染色的。
在第三章中,获得了以下两个结果:
(1).每个不包含4-圈的平面图是无圈6-可选择的;
(2).每个不包含4-圈并且任意两个三角形之间的距离至少是3的平面图是无圈5-可选择的。