图的强边着色问题的研究

发布时间：2020-08-23 19:27

【摘要】：图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
【分类号】：O157.4

【相似文献】

相关期刊论文 前10条

1 曾若溪;;青春的五种颜色[J];初中生;2017年Z1期

2 马建宁;陈瑗;;体现《纲要》精神的教育资源[J];幼儿教育;2003年01期

3 关进琴;调用控制面板的小门道[J];电脑爱好者;2000年10期

4 董伟;;有关满着色的一些结果[J];商丘师范学院学报;2006年02期

5 蔡建生;王光辉;闫桂英;;大围长图的广义无圈染色[J];数学学报;2013年01期

6 于罡;宋海洲;;正则图的均匀边染色[J];华侨大学学报(自然科学版);2010年06期

7 ;Q&A[J];数码摄影;2011年10期

8 汪国华;;开放容量 宽洋MP4++ S800 PMP播放器[J];个人电脑;2007年06期

9 ;“叫兽”支招 “色弱”本本校正秘法[J];电脑爱好者;2010年05期

10 廖福斌;“涂色”,如何不重不漏?(高二、高三)[J];数理天地(高中版);2005年07期

相关会议论文 前1条

1 王新明;;色视觉的量化检查[A];第七届全国信息获取与处理学术会议论文集[C];2009年

相关重要报纸文章 前6条

1 ;显示器故障诊断问答[N];人民政协报;2001年

2 ;PDA新品亮相EXPO展[N];中国电子报;2002年

3 太子;硬件诊室[N];中国电脑教育报;2002年

4 王军;录制动态屏幕录像[N];中国电脑教育报;2003年

5 ;商务家用两相宜[N];中国计算机报;2002年

6 江苏 张建华;Authorware课件巧优化[N];中国电脑教育报;2001年

相关博士学位论文 前2条

1 孙佳石;敦煌壁画颜色还原校正方法的研究[D];中国科学院研究生院（长春光学精密机械与物理研究所）;2005年

2 王勇;数字图像设备颜色特征化及其再现理论与技术研究[D];浙江大学;2006年

相关硕士学位论文 前6条

1 刘瑶;图的强边着色问题的研究[D];天津大学;2018年

2 董伟;有关图的满着色[D];南京师范大学;2004年

3 董新芳;路的积图的无圈点（全）染色与距离染色[D];西北民族大学;2017年

4 高志军;超立方体可区别数的研究[D];大连海事大学;2006年

5 周燕;限制边的点染色[D];山东大学;2011年

6 武波;关于图的几类着色和与强度的研究[D];山东科技大学;2008年

本文编号：2801925