一、3-正则Halin图的剖分图的全色数（论文文献综述）
杨超[1]（2017）在《图的消圈数及相关问题研究》文中研究说明图的消圈数问题是图论的重要问题之一,它源自于计算机科学,具有很强的理论意义和实际意义.随着图的消圈数问题在生产实践中被广泛应用,它逐渐成为众多学者研究的重要领域之一.截至目前,对消圈数问题的研究,已有了较为丰富的结果,并且这些结果仍在进一步完善之中.本文对消圈数及其相关问题进行了研究,全文共分为八章.第一章,介绍图论的一些相关背景和基本概念;列举了本文的主要工作.第二章,给出了消圈数的相关概念,介绍了平面图、立方图、超立方图、笛卡尔乘积图的消圈数的发展现状.第三章,从图的独立集和覆盖集的角度出发,给出两种计算图的消圈数的新公式:（1）▽（G）= n-T max {α（G-E（T））};（2）▽（G）=T min {/β（G-E（T））},其中,T为G的生成树,α（G-E（T））:β（G-E（T））分别为余树G-E（T）的独立数和覆盖数.截至目前,关于稠密图消圈数的研究工作所知甚少,而上述公式则可以直接用来计算一些稠密图的消圈数.第四章,给出了一种计算k-正则图消圈数的新公式,▽（G）=c（G）+m（S）/k-1其中,c（G）=‖ G ‖-丨G丨+1,m（W）= c + ｜E（S）｜-1,c和｜E（S）｜分别表示G-W的分支数和导出子图G[S]的边数.在此基础上,解决了 3-正则图的消圈数,凭借3-正则图的消圈数,进一步得到了 3-正则图的一个顶点划分、点荫度以及邻点可区别全染色数.第五章,研究了结构较特殊的近4-正则Halin图,并得到了三类含毛毛虫结构的近4-正则Halin图的消圈数.第六章,研究了一类平面三角剖分图GnK4,并解决了此类图在n = 1,2,3,4时的消圈数.第七章,弱化了消圈数的条件,提出消除图中最短圈的概念,并得到（?）其中,（?）s（G）表示消去图G中所有最短圈所需要去掉的最少点数.第八章,给出了图的消圈数中几个可研究的课题.
刘新月[2]（2014）在《图的（p,1）-全标号和非正常标号》文中提出图的标号问题是图论研究的主要问题之一,它有着丰富的理论内容和应用背景.图标号问题的一种实际应用背景源于频道分配问题：某一区域有若干电台,不同电台要使用不同频率的无线电波发送信号.为避免相互干扰,位置十分接近的电台要使用相差足够远的频率；位置较近的电台要使用有一定相差的频率.将频道分配给电台,目标是在保证电台互不干扰的前提下使用最少的频道资源.受此问题启发,Griggs和Yeh引入了L（2,1）-标号.2000年,G.J. Chang[5]等人将其推广到了L（p,1）-标号,这个问题在许多文献中有过研究Whittcscy[6]等人研究了图G的剖分图的L（2,1）-标号.图G的剖分图s1（G）是在图G的每条边上插入一个点得到的图.图s1（G）的L（p,1）-标号对应原图G的（p,1）-全标号.定义1.2.1图的一个k-L（2,1）-标号是从其顶点集V（G）到非负整数集{0,1,…,k}的一个映射f：V（G）→{0,1,…,k},使得：（1）对G中任意两点u,v,若d（u,v）=1,则|f（u）-f（v）|≥2；（2）对G中任意两点u,v,若d（u,v）=2,则|f（u）-f（v）|≥1.使得图G存在k-L（2,1）-标号的最小正整数k,称为图G的L（2,1）-标号数,记为λ（G）.与此相似,我们可以定义L（p,1）-标号.定义1.2.2图的一个k-L（p,1）-标号是从其顶点集V（G）到非负整数集{0,1,…,k}的一个映射f：V（G）→{0,1,…,k},使得：（1）对G中任意两点u,v,若d（u,v）=1,则|f（u）-f（v）|≥p；（2）对G中任意两点u,v,若d（u,v）=2,则|f（u）-f（v）|≥1.使得图G存在k-L（p,1）-标号的最小正整数k,称为图G的L（p,1）-标号数,记为λp（G）.定义1.2.3图G的（p,1）-全标号是对图G的顶点和边的一个标号分配,即存在映射f:V（G）∪E（G）→{0,1,…,k),使得：（1）G中任意相邻两点u,v,有|f（u）-f（u）|≥1；（2）G中任意相邻两边e,e’,有|f（e）-f（e’）|≥1；（3）G中任意相关联的点u和边e,有|f（u）-f（e）|≥p.称这样的一个分配为图G的（p,1）-全标号.（p,1）-全标号的跨度为两个标号差中的最大值.图G的（p,1）-全标号的最小跨度称为（p,1）-全标号数,记作λTp（G）不难看出,图的（p,1）-全标号是加强了条件的全染色问题,即还要求任意一点与其关联边的标号至少相差p.Havet和yu提出了图的（p,1）-全标号,并研究了λTp（G）的平凡上下界.证明了对任意图G,均有λTp（G）≥△+p-1,λTp（G）≤2△（G）+p-1,并提出了猜想λTp（G）≤min{△（G）+2p-1,2△（G）+p-1} Havet[8]改进了（2,1）-全标号的某些结果,得到了若△（G）≥2,则λTp（G）≤2△（G） Havet和yu猜想若G为连通图,△（G）≤3,且G≠K4,则λTp（G）≤5.图G的最大平均度mad（G）是其所有真子图的平均度的最大值,即mad（G）=max{2|E（H）|/|V（H）|,H∈G}.本文所研究的图都是无向简单图.在本文的第二章中,我们研究了图的（p,1）-全标号,主要得到了如下结论：定理2.1.4若G为连通平面图,△（G）≤3,最大平均度mad（G）<9/4,则λ2T（G）≤5.定理2.1.5若G为连通平面图,△（G）≤4,最大平均度mad（G）<5/2,则λT2（G）≤7.定义2.2.1任意连通图G,其顶点集为V（G）={v1,v2,…,vn}.G’表示G的复制图,顶点集为V（G’）={v’1,v’2,…,v’n},倍图D（G）构造如下：把G中每个顶点和G’中对应复制点连接起来,即：V（D（G））=V（G）∪V（G’）,E（D（G））=E（G）∪E（G’）∪{v1v’1,v2v’2,…,vnv’n}.定理2.2.5Gn表示阶为n的圈,则λTp（D（Cn））=p+3,若n三0（mod2）；p+3≤λTp（D（Cn））≤p+4,若n≡1（mod2）.定义2.2.2Fm表示阶为m+1的扇,当n个扇Fm的扇心连成圆时,用Cn·Fm表示,记V（Cn）={v1,v2,…,vn),则V（Gn·Fm）=V（Gn）∪{uij|i=1,2,…,n；j=1,2,…,m),E（Cn·Fm）=E（Cn）∪{viuij|i=1,2,…,n；j=1,2,…,m}∪{uijuij+1|i=1,2,…,n；j=1,2,…,m-1}.定理2.2.7若n为偶数,则λpT（Gn·Fm）=p+3,当m=1时；m+p+1≤λTp（Cn·Fm）≤m+p+2,当m≥2时,其中p≥2.定义2.2.3设G和G’表示两个简单图,其顶点集为V（G）={u1,u2,…,un}, V（G’）={v1,v2,…,vn)在G和G’之间叠加匹配：uivi,uivi+1,uivi+2,…,uivi+m,…,uivi+（n）,其中i=1,2,…,n；m=0,1,2,…,n；当i+m>n时,i+m为模n意义下的加法.这样得到的一系列图G（1）n,nG（2）n,n,…,G（n）n,n,称为图G和图G’的弱联图.定理2.2.9设Pn表示阶为n的路,则m+p+2≤λTp（P（m+1）n,n）≤m+p+4, m=0,1,2,…,n一2,n≥4.定理2.2.11设Cn表示阶为n的圈,当n为偶数时,有m+p+3≤λTp（C（m+1）n,n）≤m+p+5,m=0,1,2,…,n-1.定理2.3.6平面图G,最大度为△（G）,若其最大度点导出子图中含有奇圈,则λTp（G）≥△（G）+p.定理2.3.7平面图G,最大度为△（G）,若其最大度点导出子图是r-正则的,且△（G）一p<r,则λTp（G）≥△（G）+p.在频率分配背景下,还可能出现以下情况：接收频率波段的某些站点已坏掉或不受控制.反映在标号问题中,可允许某些顶点标号不受限制.对此,可研究非正常的标号问题.定义3.1.1p,q,r,s为非负整数,其中p≥q.图G的非正常（r,s,p,g）-标号是对图G的顶点集的一个整数分配L,使得：（1）若d（u,v）=1,则对每一u∈V（G）,除N（u）中至多r个顶点外,有|L（u）-L（v）|≥p；（2）若d（u,v）=2,则对每一u∈V（G）,除{v|d（u,v）=2}中至多s个顶点外,有|L（u）-L（v）f≥q.图G的非正常（r,s,p,q）-标号的最小跨度,记作λ（r,s）（G；p,q）称为G的λ（r,s）（G；p,q）数.若任意两个相邻顶点u,v不满足上述条件,即有|L（u）-L（v）|≤p,则称v为u的坏点,反过来,u也称为v的坏点；若距离为2的两个点u,v也不满足上述条件,即有|L（u）-L（v）|≤q,则称v为u的坏点,同时u也称为v的坏点.在图G中,若对任意两个坏点u和v,均有L（u）=L（v）,则由此得到的图G的一个非正常（r,s,p,q）-标号称为图G的一个非正常（r,s,p,q）’-标号.将这个非正常（r,s,p,q）’-数记作λ（r,s）（G；p,q）.在本文的第三章,我们主要得到了如下结论：定理3.1.3平面图G,不含4到9圈,p,g,r,s为正整数,p≥q,G的最大度为△,则λ（r,s）（G；p,q）≤（2q-1）（△-r-s）+4p+4q-4.
方香[3]（2013）在《关于完全扩容图的自同构群及其若干性质研究》文中研究指明本文研究了完全扩容图在连通、局部连通条件下的Hamilton性和圈扩张性.刻画了kn的完全扩容图的自同构群.最后合理的将完全扩容图利用等比数列的前r项和公式结合起来，构造了一个更大规模且有规律的图类，并给出了这类图的诸多性质.
孔元[4]（2011）在《关于几类图的分数色数与分数全色数的研究》文中提出图的着色问题是图论中的一个重要研究课题之一.分数着色是顶点着色的一个推广,对于某些具体问题,它能更好地刻画解决,分数色数作为图的重要参数之一,是非常具有研究价值的.在第二章中,首先给出了图的分数色数的几种等价定义,接着研究了几类特殊图的分数色数,包括星图,风车图及在此基础上扩充的相应的冠图及齿轮图.在第三章中,首先介绍了循环图和图的邻接矩阵的定义,然后通过构造图的最大独立集,研究了两类6-正则循环图的分数色数.在第四章中,介绍了广义Peterson图的概念及它的等价定义,考虑并研究了k=3时的广义Peterson图的分数色数.在第五章中,根据全着色猜想研究了几类Mycielski图的分数全染色,包括星图,扇图,轮图和皇冠图Gn,2,拓展了图染色的领域,便于更好地研究图的结构.
陈丽华[5]（2009）在《与频道分配有关的两类图染色问题》文中研究表明图的染色问题是图论的主要研究领域之一,是图论研究中很活跃的一个课题.它在组合分析和实际生活中有广泛的应用.随着科技的发展,经典的各类染色已经不能满足要求,于是产生了许多新的染色.设G是一个无环边的图.G的顶点正常k染色是指k种颜色1,2,…,k对于G的各顶点的一种分配,使得任意相邻的顶点被染上不同的颜色.令χ（G）=min{k|G是k色可染的},称χ（G）为G的点色数,有时简称为色数.图G的边正常k染色是指k种颜色1,2,…,k对E（G）中元素的一种分配,使得相邻两条边所染颜色不同。令χ′（G）=min{k|G是边k色可染的}称为G的边色数.Gringgs和Yeh引进了L（2,1）-标号,它的自然推广是L（p,1）-标号.图G的一个L（p,1）-标号是从V（G）到一个整数集合的映射L,必须满足:对于任意的顶点u,v（1）若dG（u,v）=1,则|L（u）-L（v）|≥p;（2）若dG（u,v）=2,则|L（u）-L（v）|≥1.图G的L（p,1）-标号在频率分配中有很强的应用背景.Whittleseyet等人在文章中研究了图G的第一剖分图的L（2,1）-标号.图G的第一剖分图s1（G）是图G通过在每条边上加一个点得到的.图s1（G）的L（p,1）-标号对应于从V（G）∪E（G）到一个整数集合的映射,这个映射必须满足:（1）图G的任意两个相邻的顶点得到不同的整数;（2）图G的任意两个相邻的边得到不同的整数;（3）图G的任意一个顶点和它所关联的边得到的整数必须至少相差p.我们把这种映射称为图G的（p,1）-全标号.一个（p,1）-全标号的跨度是指最大标号数与最小标号数的差.图G的所有（p,1）-全标号中最小的跨度,称为图G的（p,1）-全标号数,记为λpT（G）.目前对图的（p,1）-全标号的研究还比较初步.Fr（?）d（?）ic Havet和Min-Li Yu在文章中给出了λpT（G）的平凡的上下界,提出了（p,1）-全标号猜想:λpT≤△（G）+2p-1.文章中的泛宽度染色是新提出的另一种在频率分配问题上有很强应用的一种染色.泛宽度染色是对点染色的推广,是对图顶点的一种剖分.要求把所有的顶点剖分成宽度两两不同的i-宽度箱Xi,即同一宽度箱Xi中任两点的距离大于1,Xi中的顶点用同一种颜色来染.不同的宽度箱所染的颜色必须两两不同.图G的泛宽度色数χρ（G）=min{k|G是k-泛宽度可染的}.在本文第一章中,我们主要介绍了文章所涉及的一些概念、术语和符号和图染色问题的发展情况.在第二章中,我们研究了图的（p,1）-全标号,其中包括外平面图,二部图,正则图,Halin图以及定义的一种新图.第三章中研究了图的泛宽度染色,给出了二部图和Mycielskian-图的泛宽度色数的最好可能上界,给出了几类特殊图的泛宽度色数.在本文中,我们主要得到如下结论:定理2.1.4若图G是一个2-连通外平面图,且不含三角形,△（G）=3,当p≥3时,有λpT（G）=p+3.定理2.2.2若图G是一个二部图,非正则,△（G）=3,且图G中包含一个相邻于两个最大度点的最大度点,则λ2T（G）=5.定理2.2.4若图G是一个二部图,非正则,△（G）=4,且图G的最大度生成子图G△中包含K1,3,那么λ2T（G）=6.定理2.3.1若p＞χ（G）+χ′（G）-2,并且图G是边色数χ′（G）=△（G）的△-正则图,则λpT（G）=χ（G）+χ′（G）+p-2.定理2.3.2若G是一个3-正则图并且含有1-因子,则有λpT（G）≤p+5.定理2.3.3图G是3-正则图,且χ（G）=3,p＞3,则λpT（G）≥p+4.定义2.4.1若对于3-连通平面图G,去掉G中某个面f0的边界上的所有边后,G变成一棵树,并且属于V（f0）的所有顶点的度数是3,那么把G称作Halin图.属于V（f0）的顶点称为G的外部点,其余的顶点称为G的内部点.定理2.4.3图G是一个3-正则Halin图,则5≤λ2T（G）≤6.定理2.4.5图G是一个Halin图,且△（G）=4,则λ2T（G）≤6.定义2.5.1 G表示任意一个连通图,其中V（G）={v1,v2,…,vn).G′表示图G的复制图,其中V（G′）={v′1,v′2,…v′n,}.新图D（G）是由图G,G′经过下述构造得到的图:把图G中的每个顶点和图G′中所对应的复制点连起来,其中V（D（G））=V（G）∪V（G′）,E（D（G））=E（G）∪E（G′）∪{v1v′1,v2v′2,…,vnv′n,},不妨称为双图D（G）.定理2.5.1 Cn表示一个圈,则λ2T（D（Cn））=5.定理2.5.2对于任意的连通图G,满足λ2T（G）=△+4,那么双图D（G）的全标号数λ2T（D（G））≤λ2T（G）+1.定理3.1.1对任意的自然数m,n,Gm,n是二部图,我们有χρ(Gm,n)≤min{m,n}+1,并且这个上界是最好可能的.简单图的Mycielskian-图在研究图染色问题的临界性上有重要的应用,我们这里研究简单图的Mycielskian-图的泛宽度染色.定理3.1.4 G是简单图,且|G|=n.M（G）表示G的Mycielskian-图,则χρ（M（G））≤n+2.并且这个上界是最好可能的.另外我们还研究了一些特殊图类的泛宽度染色.
侯建锋[6]（2009）在《图上有限制条件的几类染色问题的研究》文中认为对图论的研究已经有二百多年的历史,最早关于图论的文章是在1736年由欧拉完成的,该文章解决了着名的哥尼斯堡七桥问题,自20世纪60年代以来,图论得到了迅猛发展,图论方面的结果大量涌现,其中图的染色理论在图论研究中占有重要的地位,图的染色理论在最优化,计算机理论,网络设计等方面都有着重要的应用,例如在网络中的数据传输,Hessians矩阵的计算等方面,本文旨在讨论图上有限制条件的几类染色问题,包括无圈染色,全染色,列表染色和f-染色。本文所考虑的图都是有限简单图,我们用V（G）和E（G）分别表示图G的顶点集和边集,图G正常的k-全染色是指用k种颜色对V（G）∪E（G）中的元素进行着色,使得相邻的或者相关联的两个元素染不同的颜色;使图G存在正常的k-全染色的最小正整数k称为G的全色数,记为x″（G）。同样的,如果我们只对图G的顶点或者边的进行着色,分别可以得到图G的点色数x（G）和边色数x′（G）。图G的一个正常的点（或者边）染色称为无圈的,如果图G中不含2-色圈,换句话说,图G中任何染两种颜色的点（或者边）导出的子图是一棵森林,图G的无圈色数,用a（G）表示,是使图G存在无圈点染色所需的最少颜色数。同样地,图G的无圈边色数,用a′（G）表示,是使图G存在无圈边染色所需的最少颜色数。设L是图G的一个颜色列表:对每个点v∈V（G）,给其一个颜色集合L（v）,如果图G存在一个无圈点染色φ,使得对v∈V（G）,都有φ（v）∈L（v）,则称图G是无圈L-可染的,如果对任意的颜色列表L满足:对v∈V（G）,有|L（v）|≥k,图G都是无圈L-可染的,则称图G是无圈k-可选择的。无圈染色问题作为一般染色问题的推广可用来有效的计算Hessians矩阵:如果已知Hessians矩阵是稀疏的和对称的,用有限差分方法来计算Hessians矩阵时可以转化为图的无圈染色问题。在2001,Alon,Sudakov和Zaks提出了如下猜想:猜想1.对任意图G,都有a′（G）≤△（G）+2。本文将给出关于该猜想的一些结果。对于全染色,Behzad和Vizing分别提出如下猜想,该猜想称为全染色猜想:猜想2.对任意图G,都有△（G）+1≤x″（G）≤△（G）+2。该猜想迄今还远没有解决,对平面图G,如果最大度△（G）≠6,则该猜想已经被验证,但是对一些曲面图来说,有时候全色数x″（G）可以唯一确定。确定曲面图的全色数将是本文讨论的问题之一。本文讨论的另外一个问题是列表染色,如果对图G的每个元素x∈V（G）∪E（G）,我们都其给一个染色集合L（x）,则L称为G的全列表,如果图G存在全染色φ使得对任意的元素x∈V（G）∪E（G）,都有φ（x）∈L（x）,则称图G是L-全可染的,令f:V（G）∪E（G）→N是正整数函数,如果对任意的全列表L满足:对x∈V（G）∪E（G）,有|L（x）|=f（x）,图G都是L-全可染的,则称G是f-全可选择的,使图G存在k-全可选择的最小正整数k称为图G的列表全色数,记为x″l（G）。同样地,图G的列表色数xl（G）或列表边色数x′l（G）分别是对G的顶点或边进行着色。列表染色是由Vizing,Erd（o|¨）s,Rubin和Taylor分别提出的,下面猜想的（a）部分是由Vizing,Gupta,Albertson和Collins,Bollobas和Harris分别提出的,该猜想被称为列表染色猜想,（b）部分是由Borodin,Kostochka和Woodall等人提出的。猜想3.如果图G是多重图,则有:（a）x′l（G）=x′（G）,（b）x″l（G）=x″（G）。对于猜想3,目前只有有限的几个结果。边染色中着名的Vizing定理表明:对最大度为△（G）的图G,有△（G）≤x′（G）≤△（G）+1。结合猜想3以及Vizing定理和全染色猜想,显然有下面的猜想:猜想4.对任意图G,都有（a）x′l（G）≤△（G）+1,（b）x″l（G）≤△（G）+2。对简单图G,由Vizing定理可知,x′（G）=△（G）或者x′（G）=△（G）+1。有了这个结果,自然地可根据边色数把所有的图划分成两类:如果x′（G）=△（G）,我们称图G是第一类的;否则称其为第二类的。在1986年,Hakimi和Kariv将正常边染色推广到f-染色,并得到许多漂亮的结果,设f是给每个顶点υ∈V（G）分配一个正整数f（v）的函数。图G的一个f-染色是G的一个边染色使得任何一种颜色在顶点v处至多出现f（v）次,使G存在一个f-染色所用的最少颜色数称为G的f-色数,记作x′f（G）。如果对任意的v∈V（G）,都有f（v）=1,则f-染色问题就变成经典的边染色问题。令△f（G）=max{[d（v）/f（v）]:v∈V（G）}。Hakimi和Kariv得到如下结论:对任意图G,都有△f（G）≤x′f（G）≤△f（G）+1。自然地,所有的简单图都可根据它们的f-色数将其划分成两类。更确切地,如果x′f（G）=△f（G）,则称G是f-第一类的;否则称G是f-第二类的。如果连通图G是f-第二类,并且满足对任意的e∈E（G）均有x′f（G-e）＜x′f（G）成立,则称G是f-临界图。本文主要考虑图上有限制条件的几类染色问题,具体的说,我们主要讨论图的无圈染色,全染色,列表染色和f-染色。本文分五章进行讨论,在第一章,我们给出一个相对完整的简介:首先,我们介绍一些图论中的基本概念和定义,然后,给出几类图上有限制条件的染色的定义和历史,最后给出本文的主要结论。在第二章,我们主要讨论图的无圈边染色以及无圈列表染色。首先我们用组合方法研究图的无圈边染色,在第2.2节,我们得到平面图的无圈边色数的一个上界,此结果比着名数学家Alon得到的结果要好,同时,我们还对猜想1进行讨论,并且得到许多漂亮的结果。然后我们将完全确定外平面图的无圈边色数,据我们所知,除了树等平凡图外,外平面图是第一个无圈边色数可以唯一确定的一类图,最后我们首次讨论轮胎图的无圈列表染色,证明了每个轮胎图都是无圈8-可选择的。在第三章,我们讨论图的全染色,证明了:设G是可以嵌入欧拉示性数x（∑）≥0的曲面∑上的图,如果最大度△（G）≥10,则全色数是△（G）+1。该结果的证明比较简单,并且我们的证明思想将会有更广泛的应用,我们同时考虑不含某些圈的平面图的全染色,从而得到许多有趣的结果。在第四章,我们考虑平面图的列表染色,其中主要是列表边染色和列表全染色,首先,我们给出关于猜想4的一些结果,然后,我们考虑不含4-圈的平面图的列表边染色和列表全染色,得到关于猜想3的一些结果。在第五章,我们主要讨论图的f-染色。首先,我们给出f-临界图的一些性质,然后,给出f-临界图边数的上下界,最后,我们介绍几类其他的边染色问题。另外,我们分别在第二、三、四、五章中给出了一些需要进一步研究的问题。
毛新叶,刘信生[7]（2008）在《一些图的剖分图的邻点可区别全色数》文中研究指明对扇,轮,完全二部图作了简单的剖分,得到了它们的剖分图,并得到了其剖分图的邻点可区别全色数.
刘景发[8]（2002）在《3-正则Halin图的剖分图的全色数》文中提出研究了 3-正则Halin图的剖分图G的全色数 ,证明了 :4≤xT（G） ≤ 5 ,特别是当G的 3-度点彼此不相邻时 ,有xT（G） =4,这里xT（G）表示G的全色数
刘景发[9]（2001）在《3-正则Halin图的全色数》文中提出研究了△ （G） =3时Halin图的全色数 ,证明了 :（i）对于 3-正则的Halin图G ,有 4 ≤xT（G） ≤ 5;（ii）若将 3-正则Halin图每边剖分一次 ,则对于剖分图M 有xT（M ） =4 ,这里△ （G）表示图G的最大度数 ,xT（G）表示图G的全色数。
二、3-正则Halin图的剖分图的全色数（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、3-正则Halin图的剖分图的全色数（论文提纲范文）
（1）图的消圈数及相关问题研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 基本概念 |
| 1.2 主要工作 |
| 第二章 消圈数 |
| 2.1 引言 |
| 2.2 研究背景和发展现状 |
| 2.2.1 平面图 |
| 2.2.2 立方图 |
| 2.2.3 超立方图 |
| 2.2.4 笛卡尔乘积图 |
| 第三章 图的消圈数与独立数、覆盖数 |
| 3.1 引言 |
| 3.2 一般图的消圈数公式 |
| 3.3 应用 |
| 第四章 正则图的消圈数与顶点划分、点荫度及染色 |
| 4.1 正则图的消圈数公式 |
| 4.2 3-正则图的消圈数 |
| 4.2.1 3-正则图的消圈数与顶点划分 |
| 4.2.2 3-正则图的点荫度 |
| 4.2.3 3-正则图的顶点划分与染色 |
| 4.3 4-正则图的消圈集的刻画 |
| 第五章 Halin图的消圈数 |
| 5.1 引言 |
| 5.2 近k-正则Halin图的消圈数 |
| 5.3 含毛毛虫结构的近4-正则Halin图的消圈数 |
| 第六章 一类平面三角剖分图的消圈数 |
| 6.1 引言 |
| 6.2 平面三角剖分图G_(nK_4)的消圈数 |
| 第七章 两类笛卡尔乘积图的最短圈 |
| 7.1 引言 |
| 7.2 定理7.1的证明 |
| 7.3 定理7.2的证明 |
| 第八章 总结与展望 |
| 参考文献 |
| 发表文章目录 |
| 致谢 |
（2）图的（p,1）-全标号和非正常标号（论文提纲范文）
| 中文摘要 |
| ABSTRACT |
| 第一章 引言 |
| §1.1 基本术语与符号 |
| §1.2 图的染色问题的发展及其推广 |
| 第二章 图的(p,1)-全标号 |
| §2.1 稀疏图的(2,1)-全标号 |
| §2.2 几类特殊图的(p,1)-全标号 |
| §2.3 图的(p,1)-全标号的下界 |
| 第三章 图的非正常标号 |
| §3.1 图的非正常(r,s,p,q)-标号 |
| 参考文献 |
| 在学期间发表的学术论文 |
| 致谢 |
（3）关于完全扩容图的自同构群及其若干性质研究（论文提纲范文）
| 中文摘要 |
| ABSTRACT |
| 引言 |
| 第一章 预备知识 |
| 1.1 基本概念 |
| 1.2 扩容图及其相关性质 |
| 第二章 完全扩容图的圈性质 |
| 2.1 相关结论 |
| 2.2 完全扩容图的 Hamilton 性 |
| 2.3 完全扩容图的点圈扩张性 |
| 第三章 K n的完全扩容图的自同构群 |
| 3.1 主要结论及证明 |
| 第四章 等比扩容图 |
| 4.1 等比扩容图的概念 |
| 4.2 主要结论及证明 |
| 参考文献 |
| 附录 1 |
| 附录 2 |
| 致谢 |
（4）关于几类图的分数色数与分数全色数的研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 1 绪论 |
| 1.1 问题的提出 |
| 1.2 国内外研究现状 |
| 1.3 基本符号和术语 |
| 1.4 论文的主要研究内容与安排 |
| 2 某些图类的分数色数 |
| 2.1 研究背景及预备引理 |
| 2.2 主要结果及其证明 |
| 3 两类6-正则循环图的分数色数 |
| 3.1 循环图的定义 |
| 3.2 主要结果及其证明 |
| 4 一类广义Peterson图的分数色数 |
| 4.1 广义Peterson图的定义 |
| 4.2 主要结果及其证明 |
| 5 平面图的Mycielski图的分数全着色 |
| 5.1 预备知识 |
| 5.2 主要定理及其证明 |
| 6 结束语 |
| 致谢 |
| 参考文献 |
| 硕士期间的主要成果 |
（5）与频道分配有关的两类图染色问题（论文提纲范文）
| 中文摘要 |
| 英文摘要 |
| 第一章 引言 |
| 第二章 图的(p,1)-全标号 |
| §2.1 外平面图的(p,1)-全标号 |
| §2.2 二部图的(2,1)-全标号 |
| §2.3 正则图的(p,1)-全标号 |
| §2.4 Halin图的(2,1)-全标号 |
| §2.5 双图的(2,1)-全标号 |
| 第三章 图的泛宽度染色 |
| §3.1 二部图和Mycielskian-图的泛宽度染色 |
| §3.2 几类特殊图的泛宽度染色 |
| 参考文献 |
| 在学期间发表的学术论文 |
| 致谢 |
（6）图上有限制条件的几类染色问题的研究（论文提纲范文）
| 中文部分 |
| 中文摘要 |
| 英文摘要 |
| 符号说明 |
| 第一章 绪论 |
| 1.1 基本定义和符号 |
| 1.1.1 图和染色 |
| 1.1.2 一些特殊图及"充放电"技术 |
| 1.2 几类有限制条件染色的概念和历史 |
| 1.2.1 无圈染色和无圈列表染色 |
| 1.2.2 全染色 |
| 1.2.3 列表染色 |
| 1.2.4 f-染色 |
| 1.3 主要结果 |
| 第二章 图的无圈染色以及无圈列表染色 |
| 2.1 预备知识 |
| 2.2 平面图的无圈边染色 |
| 2.2.1 较小的上界 |
| 2.2.2 围长较大的平面图 |
| 2.3 不含特定长度的圈的平面图 |
| 2.3.1 结构性质 |
| 2.3.2 定理2.3.1的证明 |
| 2.3.3 定理2.3.2的证明 |
| 2.4 系列平行图 |
| 2.5 外平面图 |
| 2.5.1 一个结构引理 |
| 2.5.2 α′(G)的一个小的上界 |
| 2.5.3 最大度Δ(G)≤4的外平面图 |
| 2.6 轮胎图的无圈列表染色 |
| 2.6.1 一个有用的结构引理 |
| 2.6.2 定理2.6.1的证明 |
| 2.7 需要进一步讨论的问题 |
| 第三章 图的全染色 |
| 3.1 简介 |
| 3.2 可以嵌入欧拉示性数为x(∑)≥0的曲面∑上的图 |
| 3.2.1 曲面图的一个结构引理 |
| 3.2.2 定理3.2.1的证明 |
| 3.2.3 进一步的讨论 |
| 3.3 最大度为Δ(G)≥8的平面图G |
| 3.4 最大度较小的平面图 |
| 3.5 进一步研究的问题 |
| 第四章 图的列表染色 |
| 4.1 简介 |
| 4.2 列表边色数和列表全色数的界 |
| 4.2.1 列表全色数的界 |
| 4.2.2 列表边色数界 |
| 4.3 不含4-圈的平面图 |
| 4.4 进一步研究的问题 |
| 第五章 图的f-染色 |
| 5.1 预备知识 |
| 5.2 f-临界图的性质 |
| 5.3 f-临界图边数的上下界 |
| 5.4 其他边染色问题 |
| 5.4.1 正常的边染色 |
| 5.4.2 线性染色 |
| 5.4.3 树染色 |
| 5.5 进一步研究的问题 |
| 参考文献 |
| 致谢 |
| 作者简介 |
| 学位论文评阅及答辩情况表 |
| 英文部分 |
| Chinese Abstract |
| English Abstract |
| Symbols |
| Chapter 1 Introduction |
| 1.1 Basic Definitions and Notations |
| 1.1.1 Graphs and Coloring |
| 1.1.2 Some Special Graphs and Discharging Method |
| 1.2 The Definitions and History of Restricted Coloring |
| 1.2.1 Acyclic and Acyclic List Coloring |
| 1.2.2 Total Coloring |
| 1.2.3 List Coloring |
| 1.2.4 f-Coloring |
| 1.3 Outline and Main Results |
| Chapter 2 Acyclic and Acyclic List Coloring of Graphs |
| 2.1 Preliminaries |
| 2.2 Acyclic Edge Coloring of Planar Graphs |
| 2.2.1 The Lower Bound |
| 2.2.2 Planar Graphs with Large Girth |
| 2.3 Planar Graphs without Cycles of Specific Length |
| 2.3.1 Structural Properties |
| 2.3.2 Proof of Theorem 2.3.1 |
| 2.3.3 Proof of Theorem 2.3.2 |
| 2.4 Series-Parallel Graph |
| 2.5 Outplanar Graphs |
| 2.5.1 A Useful Structural Lemma |
| 2.5.2 A Lower Bound of α′(G) |
| 2.5.3 Outerplanar Graphs with Δ(G)≤4 |
| 2.6 Acyclic List Coloring of Toroidal Graphs |
| 2.6.1 A Useful Structural Lemma |
| 2.6.2 The Proof of Theorem 2.6.1 |
| 2.7 Problems for Further Research |
| Chapter 3 Total Coloring of Graphs |
| 3.1 Introduction |
| 3.2 Graphs Embedded in A Surface ∑ of Euler Characteristic x(∑)≥0 |
| 3.2.1 A Structural Property of Embedded Graphs |
| 3.2.2 The Proof of Theorem 3.2.1 |
| 3.2.3 Further Discussions |
| 3.3 Planar Graphs G of Maximum Degree Δ(G)≥8 |
| 3.4 Planar Graphs of Small Maximum Degree |
| 3.5 Problems for Further Research |
| Chapter 4 List Coloring of Graphs |
| 4.1 Introduction |
| 4.2 Lower Bound of List Total and List Chromatic Number |
| 4.2.1 Lower Bound of List Total Chromatic Number |
| 4.2.2 Lower Bound of List Edge Chromatic Number |
| 4.3 Planar Graphs without 4-Cycles |
| 4.4 Problems for Further Research |
| Chapter 5 f-coloring of Graphs |
| 5.1 Preliminaries |
| 5.2 Properties of f-Critical Graphs |
| 5.3 Bounds on the Number of Edges of f-Critical Graphs |
| 5.4 Other Edge-Coloring Problems |
| 5.4.1 Proper Edge-Coloring |
| 5.4.2 Linear Coloring |
| 5.4.3 Tree Coloring |
| 5.5 Problems for Further Research |
| References |
| Acknowledgements |
| Curriculum Vitae |
| 学位论文评阅及答辩情况表 |
（9）3-正则Halin图的全色数（论文提纲范文）
| 0 引言 |
| 1 主要结果 |
四、3-正则Halin图的剖分图的全色数（论文参考文献）
- [1]图的消圈数及相关问题研究[D]. 杨超. 华东师范大学, 2017(05)
- [2]图的（p,1）-全标号和非正常标号[D]. 刘新月. 山东师范大学, 2014(08)
- [3]关于完全扩容图的自同构群及其若干性质研究[D]. 方香. 内蒙古师范大学, 2013(S2)
- [4]关于几类图的分数色数与分数全色数的研究[D]. 孔元. 山东科技大学, 2011(05)
- [5]与频道分配有关的两类图染色问题[D]. 陈丽华. 山东师范大学, 2009(10)
- [6]图上有限制条件的几类染色问题的研究[D]. 侯建锋. 山东大学, 2009(05)
- [7]一些图的剖分图的邻点可区别全色数[J]. 毛新叶,刘信生. 佳木斯大学学报(自然科学版), 2008(02)
- [8]3-正则Halin图的剖分图的全色数[J]. 刘景发. 南华大学学报(理工版), 2002(04)
- [9]3-正则Halin图的全色数[J]. 刘景发. 铁道师院学报, 2001(04)