首页> 正文

关于图染色中若干参数的研究

2020-11-28阅读(1068)

关于图染色中若干参数的研究

论文摘要

本学位论文主要考虑图的染色问题。图的染色理论是图论研究的重要内容之一。随着实际问题的需要,各种各样的图染色问题已被国内外的学者广泛研究和推广,如均匀染色、点（边）可区别染色、邻强边染色、列表染色等。由于确定一个图的点（边）色数是NP—完全问题,因此,确定图的这些特殊染色同样是NP—完全的。目前对这些问题的讨论基本上限制在一些具有一定条件下的图的这些特殊染色。本学位论文共分五章,主要考虑无短圈平面图的边染色、点可区别染色、均匀列表染色、均匀染色和一些其它类型的染色。其中在第一章,我们将先给出与本文有关的一些概念、符号和本学位论文的结构,同时也给出了与本文有关内容的研究背景、研究历史和研究综述。在第二章,主要讨论图的边染色,在图的边染色理论中,有一个众所周知的Vizing定理:对每个简单图G,有△（G）≤x′（G）≤△（G）+1。根据这一定理,将简单图划分为两类:满足x′（G）=△（G）的图称为第一类图;满足x′（G）=△（G）+1的图称为第二类图。在过去的若干年中,已经确定了一系列的第一类或第二类图。Vizing证明了每个△（G）≥8的平面图是第一类的。同时猜测:每一个6≤△（G）≤7的简单平面图都是第一类的。Sanders与Zhao以及Zhang各自独立地解决了△（G）=7时的Vizing猜测。至此,Vizing的平面图猜测只在△（G）=6时尚未解决。我们在这一章主要讨论△（G）=6的平面图的分类问题。证明了:若平面图G的最大度△=6,不含有弦4-圈,则G是第一类的;若G是最大度△=6且不含有弦5-圈和有弦6-圈的平面图,则G是第一类图;每个△（G）=6且不含6-圈的平面图也是第一类的。同时讨论了一类平面图的边-面染色。在第三章,我们探讨了点可区别染色问题。最初对这个问题的考虑来自于不规则网络。1997年,Burris和Schelp将这个问题限制到染色问题上,提出了点可区别边染色。同时,J.Cerry,M.Hornak和R.Sotak也独立提出了相似的概念。张忠辅等人于2000年将点可区别边染色定义中的条件弱化,提出了邻强边染色概念,并提出如下猜想:对于|V（G）|≥3的连通简单图G,G≠C5,有x′α（G）≤△（G）+2。就目前而言,有关这方面的结论很少,只知道一些特殊的图类如:树、Halin图、最大度为4的外平面图、二部图和最大度为3的图满足该猜想。在本章,我们主要围绕这一猜想展开讨论。证明了:着图G没有孤立边,g（G）≥6,则x′α（G）≤△（G）+2;若图G是阶至少为5,△（G）=4并且没有孤立边的图,则有x′α（G）≤8。图的均匀染色研究历史相对较长,早在1964年,Erd（?）s就猜测:任何一个图G和整数k≥△（G）,G有一个（k+1）-均匀染色。这一猜测于1970年被Hajnal和Szemerédi所证明。均匀染色与经典染色存在较大差异,众所周知,若图G是k-顶点可染的,则对每个不小于k的整数l,图G也是l-顶点可染的。但对于一个k-均匀可染的图G和不小于k的整数l,图G未必是l-均匀可染的。在第四章,我们主要围绕Meyer于1973年提出的猜想:如果G是不为完全图和奇圈的连通图,则x?（G）≤△（G）和2003年,Kostochka,Polsmajer和West提出的猜想:对于图G,当k≥△（G）+1时,G是k-均匀可选择的展开研究,讨论了不含4-圈和7-圈的平面图,不含4-圈和6-圈的平面图。不含5-圈和6-圈的平面图和不含3-圈的平面图的均匀染色以及均匀列表染色。在第五章,我们讨论了图的色可选择性问题。一个图若满足色数与选择数相等,就称图G是色可选择的。Galvin证明了二部图的线图是色可选择;Ohba证明了如果图G满足|V（G）|≤x（G）+（2x（G））1/2,则G是色可选择的;最近,Reed和Sudakov证明了当|V（G）|≤5/3x（G）-4/3时,G是色可选择的。我们在这一章主要讨论一类色可选择的4-正则图Hn。

论文目录

  • 摘要
  • ABSTRACT
  • 第一章 绪论
  • 1.1 符号说明
  • 1.2 基本概念
  • 1.3 图的染色
  • 1.4 论文的结构和主要内容
  • 1.4.1 图的边染色
  • 1.4.2 图的点可区别染色
  • 1.4.3 图的均匀染色
  • 1.4.4 图的色可选择性
  • 第二章 平面图的边染色
  • 2.1 无弦圈平面图的边染色
  • 2.2 不含6-圈平面图的边染色
  • 2.3 2-连通平面图的边-面染色
  • 第三章 点可区别染色
  • 3.1 大围长平面图的邻强边染色
  • 3.2 最大度为4的图的邻强边染色
  • 3.3 一般图的邻强边染色
  • 3.4 联图的点可区别全染色
  • 第四章 图的均匀染色
  • 4.1 引言
  • 4.2 围长至少为6的平面图的均匀染色
  • 4.3 不含4-圈和7-圈平面图的均匀染色
  • 4.4 不含4-圈和6-圈平面图的均匀染色
  • 4.5 不含5-圈和6-圈平面图的均匀染色
  • 第五章 色数等于选择数的4-正则图
  • 5.1 问题简介
  • n的选择数'>5.2 Hn的选择数
  • n在列表全染色中的一个应用'>5.3 Hn在列表全染色中的一个应用
  • 参考文献
  • 作者在攻读博士学位期间公开发表的论文
  • 作者在攻读博士学位期间所参与的项目
  • 致谢

    • 相关论文文献

    • [1].平面图[J]. 船舶与海洋工程 2019(06)
    • [2].展馆平面图及展品分布[J]. 中外玩具制造 2020(01)
    • [3].浅议房产测绘中房产平面图的一体化管理模式[J]. 城市建设理论研究(电子版) 2019(33)
    • [4].《公园平面图》环艺[J]. 大众文艺 2019(12)
    • [5].1-平面图及其子类的染色[J]. 运筹学学报 2017(04)
    • [6].MARINTEC CHINA 2017 W3馆平面图[J]. 船舶与海洋工程 2017(06)
    • [7].MARINTEC CHINA 2017 W5馆平面图[J]. 船舶与海洋工程 2017(06)
    • [8].不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报(理学版) 2017(04)
    • [9].平面图[J]. 美术教育研究 2017(16)
    • [10].“位置与方向”的几个要点[J]. 小学生学习指导 2020(Z4)
    • [11].合理运用信息技术 重视经历活动过程——以《绘制校园平面图》为例[J]. 阅读 2020(ZE)
    • [12].运动小区平面图[J]. 大观 2019(07)
    • [13].展区平面图[J]. 集邮博览 2015(09)
    • [14].我画校园平面图[J]. 数学小灵通(5-6年级版) 2013(04)
    • [15].展区平面图[J]. 集邮博览 2013(09)
    • [16].基于光强信息的室内平面图构建方法研究[J]. 苏州科技大学学报(自然科学版) 2020(01)
    • [17].《认识建筑》[J]. 小康 2020(18)
    • [18].MARINTEC CHINA 2017 W2馆平面图[J]. 船舶与海洋工程 2017(06)
    • [19].MARINTEC CHINA 2017 W4馆平面图[J]. 船舶与海洋工程 2017(06)
    • [20].平面图的(3,1)~*-可选择性[J]. 应用数学学报 2017(04)
    • [21].“认识平面图”教学设计与评析[J]. 小学教学参考 2014(20)
    • [22].“平面图”教学设计[J]. 中小学数学(小学版) 2013(Z2)
    • [23].展位平面图[J]. 中国汽车市场 2010(36)
    • [24].展馆平面图[J]. 汽车观察 2013(11)
    • [25].不含3-圈的1-平面图的边染色[J]. 山东大学学报(理学版) 2010(06)
    • [26].急救车平面图的设计与应用[J]. 中国社区医师(医学专业) 2010(18)
    • [27].南京国际展览中心室内平面图[J]. 农业机械 2010(S2)
    • [28].南京国际展览中心广场平面图[J]. 农业机械 2010(S2)
    • [29].浅谈家装平面图绘制中的功能空间设计技巧[J]. 艺术教育 2010(10)
    • [30].原图是平面图的4-连通线图的哈密尔顿连通性（英文）[J]. 数学进展 2019(01)

    标签：;  ;  ;  ;  

    关于图染色中若干参数的研究
    下载Doc文档

    猜你喜欢

    © 2024 毕速过 版权所有 鄂ICP备12018319号-5