导读:本文包含了强边着色论文开题报告文献综述、选题提纲参考文献及外文文献翻译,主要关键词:笛卡尔,图强,最优,松驰,平面图,网格,广义。
强边着色论文文献综述
刘瑶[1](2018)在《图的强边着色问题的研究》一文中研究指出图G的强边着色是G的一个边着色,并且对于任意两条距离小于等于2的边颜色不同。图G的强边着色指数,记作χs'(G),表示图(G有强边着色所需要的最少颜色数。图的强边着色研究的核心问题是Erdos猜想:如果G的最大度为△,那么当△为偶数时,我们有χs'(G)≤5△2/4;当△为奇数时,我们有χs'(G)≤(5△2-2△+1)/4。图G的(s,t)-松弛强边着色是对强边着色的推广。给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c:E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次。图G的(s,t)-松弛强边着色指数,记作χ(s,t)'(G),表示使得图G有(s,t)-松弛强k边着色的最小k值。本文证明了以下几个结果:1.在图G中,如果mad(G)<3并且△≤4,那么χ(1,0)'(G)≤3△;2.当△=3和△=4时,对于不同的最大平均度,我们给出χ(1,0)'((G)的上界;3.如果G是平面图,最大度△≥4并且围长最少为7,那么χ(1,0)'(G)≤3△-1。(本文来源于《天津大学》期刊2018-05-10)
张卫标[2](2017)在《强边着色猜想问题的最优图》一文中研究指出着名图论专家Erds和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ~2;当最大度Δ为奇数时,χ's(G)≤1/4(5Δ~2-2Δ+1);并且给出了当Δ=4时的最优图.此处构造了一族图,并证明了当最大度为奇数时,如果Erd9s和Ne2etǐil提出的强边着色猜想成立,则猜想中的上界是最优的.(本文来源于《重庆工商大学学报(自然科学版)》期刊2017年03期)
杨子轩[3](2017)在《广义皮特森图的强边着色数》一文中研究指出设c是图G的一个边着色,称c为它的强边着色,如果对任何两条边e与e',满足下面条件之一时,c(e)≠ c(e'):(1)e与e'有一个公共的端点;(2)存在一条边e"与e和e'都相邻.一个图G的强边着色数就是G强边着色所需最小的色数,记做X's(G).给定正整数n≥3和1 ≤k≤n/2,广义皮特森图P(nkk)的点集有2n个点分别记做...,un,v1,v2,...,vn,其中点u1,u2,...,un成为内点,点v1,v2,...,vn称为外点.P(n,k)的边集合由叁种类型组成:(a)内边uiui+1,其中i + 1是模n(i=1,2,3,...,n);(b)外边vivi+k,其中i+k是模n(i=1,2,3,...,n);(c)轴uivi(i=1,2,3,...,n).在本文中,我们计算出了广义皮特森图P(n,k)(1≤k≤3)的强边着色数.(本文来源于《新疆大学》期刊2017-05-29)
赵晓丹[4](2016)在《odd图及其在研究可平面图强边着色指数问题中的应用》一文中研究指出图G=(V,E)的边着色是一个映射c:E(G)→S,使得任意两条相邻的边e和f,满足c(e)≠ c(f).图的强边着色是图的边着色并且要求在图中和同一边相邻的两条边也要着不同的颜色.换而言之,在强边着色问题中,每一种颜色的边构成一个诱导匹配.自1983年以来,图的强边着色问题引起了诸多学者的关注,他们的研究涉及图论中很多种类型的图,例如二部图、退化图、无弦图、可平面图等,这些研究结果为我们继续探究图的强边着色问题奠定了基础.关于图G的强边着色指数χ's(G),是指能够实现图G强边着色的最少的颜色数.研究图的强边着色问题最重要的是研究图的强边着色指数大小,我们希望用尽可能少的颜色数来实现图的强边着色.本文中,我们首先对强边着色问题在一些不同类型的图中已取得的结果做一个简单地总结,然后更重要的工作是利用odd图的结构性质来解决一个问题,即每一个最大度不超过△(△ ≥ 4)的可平面图G,当围长不小于 10△—4 时,有 χ's(G)≤ 2△-1.本文主要分为四章.第一章是对图论起源及其发展历程的介绍,重点介绍了图论各个发展阶段代表性的一些问题.第二章分为两节,第一节是对文章中用到的定义概念的陈述,第二节则着重对强边着色问题已有的一些结果进行简单总结,主要包括一般图的强边着色问题,二部图、退化图和无弦图的强边着色问题,可平面图的强边着色问题.第叁章是探究odd图的结构性质,分为两节,第一节是对n ≥ 4的odd图O_n的结构进行研究,第二节是对odd图O_3的结构进行研究.第四章有两节,其中第一节是利用odd图的结构性质来解决具有较大围长的可平面图强边着色问题,第二节是对本章的回顾.(本文来源于《河南大学》期刊2016-05-01)
陆惠平[5](2013)在《一类Halin图的强边着色问题的研究》一文中研究指出关于图的各种形式的边着色问题研究是图论的重要课题,本文主要研究图的强边着色问题.给定图G=(V(G),E(G)),它的强边着色(strong edge coloring)是指对图G边集E(G)的一种颜色分配,满足如果两条边有共同顶点或者有公共的邻边,那么它们的颜色是不相同的.一个图G的强边着色所需要的最少颜色的数目称为强边着色数(strong chromatic index),记为sχ'(G).Halin图G=T∪C是平面图,由至少含有4个顶点且没有2-度点的特征树T以及连接T所有叶子的伴随圈C构成.本文研究的对象是其中一类Halin图的强边着色数,即对于特征树T中除了叶子之外均为4-度点的Halin图G=T∪C,证明了sχ'(G)≤9.(本文来源于《华东师范大学》期刊2013-04-01)
薄朝升,谢德政[6](2011)在《一类平面图的强边着色》一文中研究指出图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ's(G).证明了如果图G是平面图且满足g(G)≥14,则χ's(G)≤︱5Δ2-2Δ+1/4︱,其中g(G)表示图G的围长.(本文来源于《重庆工商大学学报(自然科学版)》期刊2011年02期)
薄朝升[7](2011)在《星着色和强边着色的研究》一文中研究指出图的着色问题是图论的重要问题之一,并且在离散数学和组合分析中有着广泛的应用。很多领域所涉及的问题都与图的着色理论相关,例如:排课表问题、排序问题、存储问题等等,都是基于图的着色理论。本文主要研究了低度图的星着色和平面图的强边着色,具体内容如下:首先,综述了一般图着色概念和研究现状,例如:顶点着色、星着色、边着色、强边着色。其次,引入星着色、强边着色的定义。最后,根据一般低度图和平面图的结构,用构造的方法重新调整一些点和边的颜色,找到了一类低度图的星色数,同时证明了一类平面图的边色数满足强边着色猜想。(本文来源于《重庆大学》期刊2011-04-01)
杨清军[8](2010)在《一些特殊图的强边着色和平方自由着色》一文中研究指出为了恰当地表示大型超网络、数据库系统、时间安排和线路设计等研究课题中各元素之间的关系,边着色理论一直发挥着重要的作用。强边着色理论做为一般图的边着色的推广被自然的引入。由于其良好的应用背景,强边着色理论成为现在图论领域中迅速发展的子学科之一,也是各学者们所热衷的研究方向。自2002年Alon把平方自由的概念推广到图论中来后,平方自由着色做为一种更新的着色方式,在近10年也得到了飞速的发展,平方自由边着色、平方自由点着色、平方自由的强边着色,平方自由无循环着色等在各个领域都有着广泛的应用。图G的强边着色是指一个正常的边着色,同时对任意长为3的路上的边不能有相同的颜色,一个图G的强边色数是指G中所有强边着色中所用色数的最小者。一个有限的元素序列a1 a2 an叫做平方自由的,当且仅当该序列不包含连续的形如ww = x1 x2 xm x1 x2xm的子序列。2002年Alon把这个概念推广到图论中来,若一个图G (V , E )的边着色是平方自由的,当且仅当图G中任意一条路上所着颜色序列都是平方自由序列。本文首先综述了一般图的边着色、强边着色的概念及研究现状,研究方法等。对于这些方法的研究可间接的利用到关于特殊图的着色当中。本文中先研究了几类积图的强边着色,并给出了相应图的精确的强边色数值。紧接着介绍了关于平方自由着色的概念以及一些特殊图的平方自由边着色的研究现状。此外给出了完全k叉树和d维超立方体的一些平方自由性质,得到了一些新的结果。同时指出了文献[33]中有关命题5的错误,并给出了反例和相关的证明。(本文来源于《重庆大学》期刊2010-04-01)
张卫标,杨清军[9](2009)在《关于强边着色猜想的最优图问题》一文中研究指出着名图论专家Erds和Neetil对图的强边着色数上界提出了一个猜想:当Δ为偶数时,χ′s(G)≤5/4Δ2;当Δ为奇数时,χ′s(G)≤1/4(5Δ2-2Δ+1),他们给出了当Δ=4的时的最优图.此处构造了一族图,并以此证明了当Δ为偶数时,如果Erd s和Neetil提出的强边着色猜想成立,则猜想中的上界是最优的.(本文来源于《重庆工商大学学报(自然科学版)》期刊2009年06期)
谢德政,杨清军[10](2009)在《几类积图的强边着色》一文中研究指出图G的强边着色是指一个正常的边着色,同时对任意长为3的路上的边不能有相同的颜色.图G的强边色数是指在G的所有强边着色中所用色数的最小者.研究了几类积图的强边着色,并给出了相应图的精确的强边色数值.(本文来源于《重庆工学院学报(自然科学版)》期刊2009年04期)
强边着色论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
着名图论专家Erds和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ~2;当最大度Δ为奇数时,χ's(G)≤1/4(5Δ~2-2Δ+1);并且给出了当Δ=4时的最优图.此处构造了一族图,并证明了当最大度为奇数时,如果Erd9s和Ne2etǐil提出的强边着色猜想成立,则猜想中的上界是最优的.
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
强边着色论文参考文献
[1].刘瑶.图的强边着色问题的研究[D].天津大学.2018
[2].张卫标.强边着色猜想问题的最优图[J].重庆工商大学学报(自然科学版).2017
[3].杨子轩.广义皮特森图的强边着色数[D].新疆大学.2017
[4].赵晓丹.odd图及其在研究可平面图强边着色指数问题中的应用[D].河南大学.2016
[5].陆惠平.一类Halin图的强边着色问题的研究[D].华东师范大学.2013
[6].薄朝升,谢德政.一类平面图的强边着色[J].重庆工商大学学报(自然科学版).2011
[7].薄朝升.星着色和强边着色的研究[D].重庆大学.2011
[8].杨清军.一些特殊图的强边着色和平方自由着色[D].重庆大学.2010
[9].张卫标,杨清军.关于强边着色猜想的最优图问题[J].重庆工商大学学报(自然科学版).2009
[10].谢德政,杨清军.几类积图的强边着色[J].重庆工学院学报(自然科学版).2009