几类图的条件着色与平方着色的研究

【摘要】：图的着色问题一直是图论研究中的重要问题之一,有着重要的理论意义和实用价值.最初起源于地图的“四色猜想”,展开了对着色问题的研究.经过一个多世纪的研究,在经典的点着色与边着色的基础上,产生了许多新的着色.比如：星着色、圈着色、全着色、距离着色、无圈着色、关联着色、分数着色、条件着色以及线性着色等.近年来,图的着色研究非常活跃.其中条件着色就是近年来提出的.条件着色是赖虹建2006年在文献中被提出.平方着色是一种特殊的标号着色,标号着色出现在上世纪九十年代,它是图的一种特殊的顶点着色.近年来,通过对图的平方着色与条件着色进行研究,运用新的方法,产生了许多新的结果.本文主要研究几类特殊图的条件着色与平方着色.本文的具体内容可分为以下三部分：第一节,介绍了本篇论文的问题背景,基本概念和目前的研究现状以及我们将要研究的内容.第二节,主要对Sierpinski类型图的条件着色进行研究,首先对Sierpinski类型图进行介绍,在给出预备知识,最后给出具体的结果及其证明.第三节,主要对路与路、路与圈、圈与路和圈与圈的半强积的平方着色进行研究,首先对相关知识进行介绍,在给出预备知识,最后给出相关的结果及其证明.
【关键词】：Sierpinski图 Sierpinski gasket图 Sierpinski-like图 条件着色 半强积 平方着色
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5