一些特殊种类图的[r,s,t]-着色

摘要

图G的[r,s,t]-着色是对图论经典着色的推广.令G=(V,E)是顶点集为V,边集为E的图,给定非负整数r,s和t,图G的[r,s,t]-着色是V(G)uE(G)到色集{0,1,…,k-1}的一个函数c,满足:对于任意两个相邻的顶点vi,vj∈V,都有[c(vi)-c(uj)]≥r(称为r条件r-condition);对于任意两条相邻的边ei,ej∈E,都有[c(ei)-c(ej)]≥s(称为s-条件s-condition);对于任意一个顶点vi和与其关联的边ej,都有[c(vi)-c(ej)]≥t(称为t-条件,t-condition)图G的[r,s,t]-着色所用的最小色数k称为图G的[r,s,t]-色数,记作λr,s,t(G).本文主要研究了树和含点不交偶圈的图的[r,s,t]-色数与它们最大导出星的[r,s,t]-色数的关系.依据内容,本文分为五个部分:第一部分从历史的角度,主要介绍了图论的起源、发展及本文的选题背景.第二部分主要介绍了图和点着色、边着色、全着色及其相关结论.第三部分主要介绍了[r,s,t]-着色的基本知识、研究现状及相关引理.第四部分研究的是树的[r,s,t]-色数.通过用树TT的导出星K1,△(T)的一个[r,s,t]-着色对树T进行点、边着色,证明了树的[r,s,t]-色数等于树中最大导出星的[r,s,t]-色数.第五部分研究的是含点不交偶圈的图的[r,s,t]-色数.通过用图G的导出星K1,△(G)的一个[r,s,t]-着色对图G进行从下往上着色,证明了含点不交偶圈的图的[r,s,t]-小色数等于图中最大导出星的[r,s,t]-色数.

目录

摘要

Abstract

第一章 前言

§1.1 图论的发展

§1.2 选题背景

第二章 图及经典着色

§2.1 图的基本知识

§2.2 经典着色的基本知识

第三章 [r,s,t]-着色

§3.1 [r,s,t]-着色的基本知识

§3.2 研究现状及引理

第四章 树的[r,s,t]-着色

第五章 含点不交偶圈的图的[r,s,t]-着色

参考文献

致谢