一、Halin图和Series-Parallel图的星荫度（论文文献综述）
陶昉昀[1]（2015）在《关于图的一些荫度问题的研究》文中进行了进一步梳理图G的正常k-全染色是指用k种颜色给V（G）∪ E（G）中的元素进行染色,使得任意两个相邻的或相关联的元素均染不同的颜色。使得图G有正常的k-全染色的最小正整数k称为G的全色数,记为χ"（G）。类似的,我们可以定义图G的正常点染色和正常边染色,对应的色数分别称为点色数和边色数,分别记为χ（G）与χ’（G）。荫度的概念可以看作是图的一种染色（不一定是正常的）,其中每个色类的导出子图是一个森林。本文研究了几种不同的荫度概念：图的线性荫度、线性k-荫度、k-星荫度、全荫度、列表全荫度和强均匀点荫度。主要内容概括如下：（1）图的线性荫度。一个线性森林是指每个连通分支都是路的森林。图G的线性荫度是指使得G可以分解成m个线性森林的最小正整数m,用la（G）表示。本文确定了完全图与路、完全图与圈,以及两个完全图的笛卡尔积图的线性荫度。（2）图的线性k-荫度。一个线性k-森林是指每个连通分支都是长度不超过k的路的森林。图G的线性k-荫度是指使得G可以分解成m个线性k-森林的最小正整数m,用lak（G）表示。本文首先研究了两个圈的笛卡尔积图的线性2-荫度,得到了确切的数值。此外,本文研究了几类特殊的平面图,分别给出了这些平面图的线性2-荫度的上界。（3）图的k-星荫度。一个星是指至多一个顶点的度大于1的树。一个k-星森林是指所有分支都是顶点数不超过k+1的星的森林。使得图G可以分解成m个k-星森林的最小正整数m,称为图G的k-星荫度,用sak（G）表示。本文讨论了最大度不超过3的图和树的k-星荫度的上下界,并给出了两个相关的算法。（4）图的全荫度和列表全荫度。在图G的一个k-全染色f（不一定是正常的）中,若每个色类的元素在全图中的导出子图是一个森林,则称f是图G的一个无圈k-全染色。使得图G有一个无圈k-全染色的最小正整数k称为图G的全荫度,记为ρ"（G）。对于图G的每个元素x,如果我们都给它指定一个颜色集合L（x）,那么我们称L为G的一个列表。设L是G的一个给定的列表,如果存在G的一个无圈全染色f,满足对任意的元素x ∈ V（G） ∪ E（G）都有f（x）∈L（x）,则称f是G的一个无圈列表全染色。若对于满是|L（x）|≥k的任意可能的列表L,G都有一个无圈列表全染色,则称G是无圈k-全可选的。使得图G是无圈k-全可选的最小正整数k称为图G的列表全荫度,记为ρl"（G）。这两个概念是Hetherington提出的。此外,他还提出了关于全荫度的猜想：对任何简单图G,均有本文完全确定了完全图Kn和完全二部图Kn,n的全荫度,证明以上猜想对这两类图是成立的。对于Halin图,我们给出了其列表全荫度的上界。本文还研究了平面图的全荫度,证明了对于△（G）≥13的平面图和△（G）≥7且不含4-圈的平面图,全荫度猜想都是成立的。（5）图的强均匀点荫度。设f是图G的顶点的一个t-染色,若每个色类的导出子图的每个分支都是最大度不超过k的树,则称f为图G的一个（t,k）-树染色。设f为图G的一个（t,k）-树染色且任何两种不同颜色所染的顶点数最多相差1,则称f为图G的一个均匀（t,k）-树染色。使得对所有的t’≥t,图G都具有均匀（t’,k）-树染色的最小正整数t,称作强均匀点k-荫度,记作vak≡（G）。吴建良等人首先提出了这个概念,并且猜想：对任何平面图G,均有va∞≡（G）=O（1）。在本文中,我们首先研究了完全二部图Kn,n的强均匀点1-荫度,得到了一些相关的结果。其次,我们研究了两类特殊的平面图,分别得到了强均匀点∞-荫度的上界,从而证明了吴建良的猜想对这两类平面图是成立的。
纪世粉[2]（2011）在《关于图的几类着色问题的研究》文中研究说明图G的关联着色σ为由I（G）到颜色集C的一个映射σ,使得I（G）中任何相邻的关联对都着不同的颜色.若σ:I（G）→C是G的关联着色且满足|C|=k,k是一个正整数,则称σ-是G的一个k-关联着色,使得G存在k-关联着色的最小值k称为G的关联色数,记作χi（G）,即χi（G）=min{|C||σ:I（G）→C是G的关联着色}.邻点可区别关联着色的定义是在关联着色的基础上推广出来的,进一步细化了图的着色参数：若对任意uv∈E（G）满足C（u）≠C（v）,则称σ为G的k-邻点可区别关联着色,并称χai（G）=min{|k|k是G的k-邻点可区别关联着色}为G的邻点可区别关联色数.本文从图的结构和性质出发,利用反证法和枚举法研究一些图的邻点可区别关联着色,定义了图的k-d-距离可区别关联着色和点可区别关联着色,并确定了几类图的k-d-距离可区别关联色数和一些图的点可区别关联色数.本文共分六章,具体安排如下：第二章中,主要给出了图论的基础知识和相关引理,并定义了三类新图.第三章中,主要研究讨论了θ-图、广义θ-图和广义星图的邻点可区别关联着色.第四章中,在图的邻点可区别关联着色的基础上定义了图的k-d-距离可区别关联着色的概念,研究了图的k-d-距离可区别关联着色的几条性质和几类图的k-d-距离可区别关联着色,确定了星Sn、扇Fn+1（n≥3）、轮Wn+1（n≥4）、圈Cn（n≥4）和向日葵图的k-2-距离可区别关联色数,以及路Pn（n≥5）的几类k-d-距离可区别关联色数.在第五章中,在图的邻点可区别关联着色和在第四章的基础上,定义了图的点可区别关联着色的概念,并讨论了几中常见图类的点可区别关联着色,确定了星图Sn、完全图Kn、扇Fn+1（n≥3）Fn+1（n≥3）、轮Wn+1（n≥4）和C5的点可区别关联色数,并确定了路Pn（n≥3）和圈Cn（n≥4）的点可区别关联色数下界.
金政国[3]（2010）在《平方图的点荫度》文中研究说明本文中考虑的图都是简单图.分别用V（G）,E（G）,|G|,Δ（G）,δ（G）表示图G的点集合,边集合,点的个数,最大度,最小度,用dG（x）表示点x的度.设G是一个图,G的一个k着色σ就是从V（G）到{1,2,…,k}的一个映射.我们用υa（G）表示图G的点荫度,它是图G的最小顶点划分数使得每一个划分集的导出子图是一个森林.设G（V,E,F）是一个3-连通平面图.f0表示G的无限外部面,E（f0）为与外部面f0相关联的边集合.如果G/E（f0）为一棵树,则称G为Halin图.同时我们称与f0不关联的点为内点.本文中研究的Halin图是指内点度至少为3的Halin图.任意两点u,υ∈υ（G）,它们之间的距离为连接这两个点的最短路的长度,用dG（υ,υ）表示.图G的平方图G2是以V（G）作为它的点集,两个点u,υ在G2中相邻当且仅当1≤dG（υ,υ）≤2.本文介绍了一些荫度的定义及主要结论,并研究了Halin图的平方图的点荫度.在第一章,我们给出了本文的背景知识、所用到的基本概念以及主要结果.在第二章,介绍了一些荫度的定义及主要结论,其中包括与点相关的荫度：点荫度、点线性荫度、点星荫度；以及与边相关的荫度：边荫度、线性荫度、毛毛虫荫度、星荫度、T—free荫度、Sn—free荫度、Pn—free荫度、K1,n—free荫度.在该章还给出了荫度方面的一些结果.在第三章,对Halin图的平方图的点荫度进行了研究.在荫度的研究领域,绝大部分的研究集中在平面图,而对于非平面图的荫度的研究目前较少.一般来说,Halin图的平方图是非平面图.杨爱峰等人在文献[33]中证明了直径为2的图的导出森林2划分问题是NP-完全问题,故图的点荫度的计算问题也是NP-完全问题.山东大学的马刚、吴建良、方俊峰在文献[38]中证明了树的平方图的点荫度是（?）.本章在树的平方图的点荫度的基础上研究了Halin图的平方图的点荫度,得到了以下两个结果：定理3.2.5.最大度小于6的Halin图G的平方图G2的点荫度满足2≤υa（G2）≤4.定理3.2.7.内点度均大于等于6的Halin图的平方图的点荫度是（?）.
闫立军[4]（2007）在《临界图的若干性质和图的关联着色的研究》文中进行了进一步梳理无环图G的一个边着色π是从边集E到颜色集C的一个映射π：E→C，使得G中任何两条相邻的边均有不同的像。若|C|=k，则称π是G的一个k-边着色。使得G有k-边着色的最小k值称为G的边色数，即：x’（G）=min{k|G存在一个k-边着色}。着名的Vizing定理表明：若G是简单图，则x’（G）≤△+1。根据边着色的定义可知x’（G）≥△。于是人们根据图的边色数将简单图分为两类，即若x’（G）=△，则称G是第一类图；若x’（G）=△+1，则称G是第二类图。设G是连通第二类图，且对G的任何边e都有：x’（G-e）＜x’（G），则称G是临界图。本文根据临界图的定义和VAL定理讨论了△≥5的临界图的若干性质，为冲击临界图猜想作了准备工作。图G的一个顶点着色φ是从顶点集V到颜色集C的一个映射φ：V→C，使得G中任何两个相邻的顶点均无相同的像。若|C|=k，则称φ是G的一个k-顶点着色。使得G有k-顶点着色的最小k值称为G的顶点色数，用x（G）表示。设I（G）={（v，e）|v∈V，e∈E且v与e相关联}是G的关联集。称G的两个关联（v，e）和（w，f）相邻当且仅当下列三种情况之一成立：（1）v=w；（2）e=f；（3）vw=e或vw=f。图G的一个关联着色σ是从关联集I（G）到颜色集c的一个映射σ：I（G）→C，使得I（G）中任何两个相邻的关联都有不同的像。若σ：I（G）→C是G的一个关联着色且|C|=k，则称G是k-可关联着色的。使得G有k-可关联着色的最小k值称为G的关联色数，用xi（G）表示。本文根据关联着色和顶点着色的定义、性质给出了关联图的两个等价定义，并在此基础上讨论了关联图的一些性质以及关联着色与顶点着色的若干关系；利用穷染法和换色技巧确定了Meredith’s图的关联色数；从图的结构性质出发，利用双重归纳法和换色技巧证明了△≥4的系列平行图都存在一个（△+2，2）-关联着色；根据（k，l）-关联着色的定义和△=4，mad（G）＜3的图的结构性质，利用归纳法和换色技巧证明了△=4，mad（G）＜3的图G存在一个（6，2）-关联着色。
王雅琴[5]（2007）在《图的关联着色与邻点可区别关联着色》文中进行了进一步梳理设图G=（V，E），I（G）={（v，e）| v∈V，e∈E，且v与e相关联}称为G的关联集。G的两个关联（v，e）和（w，f）是相邻的是指满足下列三个条件之一：（1）v=w；（2） e=f；（3） vw=e或vw=f。图G的关联着色是从I（G）到颜色集合C的一个映射σ，使得G中任何两个相邻关联具有不同的象。若(σ：I（G）→C是G的一个关联着色且|C|=k，k是一个正整数，则称G是k-可关联着色的，σ是G的一个k-关联着色；使得G是k-可关联着色的最小的k值称为G的关联色数，记为Xi（G），即Xi（G）=min{|C||σ：I（G）→C是G的关联着色}。本文研究了θ-图的关联着色，定义了图的邻点可区别关联着色及邻点可区别关联色数并确定了几类图的邻点可区别关联色数。本文共分五章，具体安排如下：我们在第二章中将确定θ-图的关联色数。在第三章中我们将定义图的邻点可区别关联着色及邻点可区别关联色数：对图G，设Qu={（u，uu’）|u’∈N（u）}∪{（u’，u’u）|u’∈N（u）}，σ：I（G）→C为图G的k-关联着色，Cu表示着在Qu上的色集。若对任意uv∈E（G）满足Cu≠Cv，则称σ为G的k-邻点可区别关联着色，并称Xai（G）=min{k|存在G的k-邻点可区别关联着色}为G的邻点可区别关联色数。我们将确定路、圈、星、扇、轮、完全图的邻点可区别关联色数。在第四章中我们将确定完全二部图、Cm·Fn图及一类θ-图的邻点可区别关联色数。在第五章中我们将确定两类联图的邻点可区别关联色数。
董桂香,许振宇[6]（2005）在《Halin图和Series-Parallel图的动态色数》文中认为图的动态着色是BruceMontgomery于2001年引入的一个新概念。本文分别证明了Halin图和非5圈的Series Parallel图的动态色数都不超过4。
董桂香[7]（2003）在《关于若干图类的着色问题》文中提出本文讨论了若干图类的四种不同的着色问题：动态着色、关联着色、平面图的完备着色和边面着色。利用构造性组合方法和换色技巧给出了Halin图和系列平行图动态色数的最小上界，并确定了一类特殊系列平行图的动态色数，确定了某些笛卡儿积图和某些联图的关联色数，确定了1-树图的完备色数并证明了有关边面着色的一个猜想。
许振宇[8]（2003）在《若干图着色问题的研究》文中研究指明本文研究了三种不同的着色：图的关联着色、无圈边着色和强边着色。分别确定树和3k-圈的膨胀图及圈、K2.n、扇图和△≥6的Halin图的一致膨胀图的关联色数。证明了Halin图、1-树和外平面图满足由N.Alon提出的任何一个图的无圈边色数不超过其最大度加2的猜想。给出了两类高度正则图的强边色数，并对A.C.Burris的一个结果进行了初步的探讨。
吴建良,贠军亮,张咏梅[9]（2000）在《Halin图和Series-Parallel图的星荫度》文中研究说明证明了：（1）所有Halin图的星荫度为3，和（2）所有SeriesParallel图的星荫度小于等于3.
二、Halin图和Series-Parallel图的星荫度（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、Halin图和Series-Parallel图的星荫度（论文提纲范文）
（1）关于图的一些荫度问题的研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 图的基本定义及符号 |
| 1.2 图的几种荫度的定义及研究概况 |
| 1.2.1 荫度、线性荫度、线性k-荫度及星荫度 |
| 1.2.2 点荫度、全荫度、列表全荫度 |
| 1.2.3 均匀点荫度和强均匀点荫度 |
| 1.3 本文主要研究内容 |
| 第二章 笛卡尔积图的线性荫度及线性2-荫度 |
| 2.1 笛卡尔积图的线性荫度 |
| 2.2 笛卡尔积图的线性2-荫度 |
| 第三章 平面图的线性2-荫度 |
| 3.1 不含相邻3-圈或不含相邻4-圈的平面图 |
| 3.1.1 结构定理 |
| 3.1.2 线性2-荫度 |
| 3.2 不含相交4-圈的平面图 |
| 3.2.1 结构定理 |
| 3.2.2 线性2-荫度 |
| 3.3 4-圈与5-圈不相邻的平面图 |
| 3.4 3-圈与5-圈不相邻的平面图 |
| 第四章 图的k-星荫度 |
| 4.1 定义及基本性质 |
| 4.2 最大度不超过3的图的2-星荫度 |
| 4.3 树的k-星荫度 |
| 第五章 图的全荫度及列表全荫度 |
| 5.1 完全图和完全二部图的全荫度 |
| 5.2 Halin图的列表全荫度 |
| 5.3 平面图的全荫度 |
| 第六章 图的强均匀点荫度 |
| 6.1 完全二部图K_(n,n)的强均匀点1-荫度 |
| 6.2 平面图的强均匀点∞-荫度 |
| 第七章 总结与展望 |
| 参考文献 |
| 附录一 个人学习经历 |
| 附录二 博士期间发表和完成的论文 |
| 附录三 博士期间参加的科研项目、学术会议 |
| 附录四 致谢 |
（2）关于图的几类着色问题的研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 1 绪论 |
| 1.1 问题研究的意义 |
| 1.2 问题提出的背景 |
| 1.3 论文的主要研究内容与安排 |
| 2 图论的基础知识 |
| 2.1 基本概念 |
| 2.2 相关引理 |
| 3 三类图的邻点可区别关联着色 |
| 3.1 θ-图的邻点可区别关联着色 |
| 3.2 广义图星图的邻点可区别关联着色 |
| 3.3 广义θ-图的邻点可区别关联着色 |
| 4 图的k-d-距离可区别关联着色 |
| 4.1 图的k-d-距离可区别关联着色的概念与性质 |
| 4.2 几类图的一些k-d-距离可区别关联着色 |
| 5 图的点可区别关联着色 |
| 6 结论与展望 |
| 致谢 |
| 参考文献 |
| 攻读硕士期间的主要研究成果 |
（3）平方图的点荫度（论文提纲范文）
| 致谢 |
| 中文摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 基本概念 |
| 1.2 荫度的研究背景 |
| 1.3 主要结果 |
| 第二章 关于图的各种荫度 |
| 2.1 与点有关的荫度 |
| 2.2 与边有关的荫度 |
| 2.3 与点有关的荫度的相关结论 |
| 2.4 与边有关的荫度的相关结论 |
| 第三章 Halin图的平方图的点荫度 |
| 3.1 预备知识 |
| 3.2 主要结论 |
| 3.3 展望 |
| 参考文献 |
| 学位论文数据集 |
（4）临界图的若干性质和图的关联着色的研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 引言 |
| 2 临界图的若干性质 |
| 2.1 基本概念与预备引理 |
| 2.2 主要结果及证明 |
| 3 图的关联着色与顶点着色的关系 |
| 3.1 基本概念与预备引理 |
| 3.2 主要结果及证明 |
| 4 Meredith's图的关联色数 |
| 4.1 基本概念与预备引理 |
| 4.2 主要结果及证明 |
| 5 系列平行图的关联着色 |
| 5.1 基本概念及引理 |
| 5.2 主要结果及证明 |
| 6 图的最大平均度与关联着色 |
| 6.1 基本概念与预备引理 |
| 6.2 主要结果及证明 |
| 致谢 |
| 参考文献 |
| 详细摘要 |
（5）图的关联着色与邻点可区别关联着色（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 图的基本知识 |
| 1.2 问题的提出 |
| 1.3 本文的主要研究内容与安排 |
| 2 θ-图的关联色数 |
| 2.1 基本概念与预备引理 |
| 2.2 主要结果 |
| 3 图的邻点可区别关联着色 |
| 3.1 定义与几个有用的定理 |
| 3.2 几类图的邻点可区别关联色数 |
| 4 三类图的邻点可区别关联色数 |
| 4.1 基本概念与预备引理 |
| 4.2 主要结果 |
| 5 两类联图的邻点可区别关联色数 |
| 5.1 主要结果 |
| 6 结束语 |
| 致谢 |
| 参考文献 |
| 详细摘要 |
（7）关于若干图类的着色问题（论文提纲范文）
| 1 引言 |
| 2 几类图的动态色数 |
| 2.1 基本概念和记号 |
| 2.2 Halin图的动态色数 |
| 2.3 Series-Parallel图的动态色数 |
| 2.4 关于联图的动态色数的界 |
| 3 1-树图的两种着色 |
| 3.1 基本概念和记号 |
| 3.2 1-树图的完备着色 |
| 3.3 1-树图的边面着色 |
| 4 几类图的关联色数 |
| 4.1 基本概念和记号 |
| 4.2 某些笛卡儿积图的关联色数 |
| 4.3 某些联图的关联色数 |
| 4.4 T_(l×m)和T_(l×m×n)的关联色数 |
| 致谢 |
| 主要参考文献 |
（8）若干图着色问题的研究（论文提纲范文）
| 1 绪言 |
| 2 若干图类的膨胀图的关联色数 |
| 2.1 引言 |
| 2.2 树和3k-圈的膨胀图的关联色数 |
| 2.3 圈和K_(2,n)的一致膨胀图的关联色数 |
| 2.4 扇图和△≥6的Halin图的一致膨胀图的关联色数 |
| 3 若干平面图的无圈边着色 |
| 3.1 引言 |
| 3.2 Halin图的无圈边色数 |
| 3.3 1-树图与外平面图的无圈边着色 |
| 4 图的强边着色 |
| 4.1 引言 |
| 4.2 高度正则图的强边色数 |
| 4.3 关于A.C.Burris的一个结果的注记 |
| 致谢 |
| 参考文献 |
四、Halin图和Series-Parallel图的星荫度（论文参考文献）
- [1]关于图的一些荫度问题的研究[D]. 陶昉昀. 东南大学, 2015(06)
- [2]关于图的几类着色问题的研究[D]. 纪世粉. 山东科技大学, 2011(05)
- [3]平方图的点荫度[D]. 金政国. 北京交通大学, 2010(06)
- [4]临界图的若干性质和图的关联着色的研究[D]. 闫立军. 山东科技大学, 2007(05)
- [5]图的关联着色与邻点可区别关联着色[D]. 王雅琴. 山东科技大学, 2007(04)
- [6]Halin图和Series-Parallel图的动态色数[J]. 董桂香,许振宇. 山东科技大学学报(自然科学版), 2005(01)
- [7]关于若干图类的着色问题[D]. 董桂香. 山东科技大学, 2003(04)
- [8]若干图着色问题的研究[D]. 许振宇. 山东科技大学, 2003(04)
- [9]Halin图和Series-Parallel图的星荫度[J]. 吴建良,贠军亮,张咏梅. 山东科技大学学报(自然科学版), 2000(04)