论文部分内容阅读
一个有序对G=(V,E)称为一个无向图，其中V和E通常是有限集合.V中的元素称为图G的顶点,E是由V中不同元素的无序对组成的集合,E中的元素称为图G的边.通常用V(G)和E(G)来表示图G的顶点集和边集.一个图G称为是平面的当且仅当它可以画在平面上,使得它的任何一条边不与另外一条边交叉. 对于正整数k, r.令k={1,2,…k}.如果 c:V(G)→k, VCV(G),那么c(V)={c(υ)|υ∈ V}.图G的(k,r)染色是这样一个映射c:V(G)→k,满足下列两个条件： (C1)对于每条边uυ∈E(G), c(u)= c(υ); (C2)对于每个点υ∈V(G),|c(NG(∈))|≥min{dG(v), r}. 条件(C2)经常被作为r-hued条件.对于整数k,r>0,图G的(k, r)染色是一个正常k染色,使得对于每一个度数为d(v)的点v, v至少表现min{d(v),r)种颜色,这样的染色,称之为r-hued染色，图G的r-hued染色数,记作Xr(G).是使图G存在( k,r)染色的最小的k值. r-hued染色是图的点染色的推广. 本学位论文主要研究了围长至少为5的平面图的r-hued染色以及一般平面图的3-hued染色. 第一章介绍研究领域的相关发展背景,研究现状和本文所要用到的基本概念. 第二章证明了围长至少为5的平面图的r-hued染色的相关结果：当3≤r≤7时,且图G是围长至少为5的平面图,则Xr(G)≤r+11.特别的,当r=3,4,5,6时，分别有 X3(G)≤10, X4(G)≤11, x4(G)≤12, X6(G)≤13. 第三章给出了一般平面图的3-hued染色的结果，即若图G是一个平面图,则 X3(G)≤12. 第四章对本文的研究结果作了简单的总结并做了进一步的展望.