曲面可嵌图的在线列表染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:PeNgxionglifanG2
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文探究曲面可嵌图的在线选择数与非正常的在线选择数。图的在线选择数是选择数的在线形式,并且它总是不小于其选择数。类似的,d-defective在线选择数是d-defective选择数的在线形式,并且它总是不小于其d-defective选择数。  在本文中,我们将选择数和d-defective选择数的一些著名的结果推广到了在线选择数和d-defective在线选择数。对于嵌入在曲面S上的图G,其边宽ew(G)为G的最短的不可缩圈的长度,其中不可缩圈是指其嵌入为S上的一条不可缩的闭Jordan曲线的圈。在1993年,Thomassen证明了对于任意给定的曲面S,存在一个常数w使得每一个边宽至少为w的S-可嵌图均可5染色。DeVos,Kawarabayashi和Mohar在2008年证明了对于任意给定的曲面S,存在一个常数w使得每一个边宽至少为w的S-可嵌图均为5-可选的。本文对上述的结论进行了扩展,证明了对于任意给定的曲面S,存在一个常数w使得每一个边宽至少为w的S-可嵌图均为在线5-可选的。  图G的d-defective染色是指G的一个顶点染色,满足每个色集的导出子图的最大度至多为d。在1986年,Cowen,Cowen和Woodall证明了每个外平面图是2-defective2-可染的,每个平面图是2-defective3-可染的。Eaton和Hull还有Skrekovski分别扩展了上述的结果,证明了每个外平面图是2-defective2-可选的,每个平面图是2-defective3-可选的。Cushing和Kierstead之后证明了每个平面图是1-defective4-可选的。本文中,我们证明了对于任意给定的曲面S,存在一个常数w使得每一个边宽至少为w的S-可嵌图均为2-defective在线4-可选的。
其他文献
摘 要 本文通过对小产权房的含义界定,对小产权房的法律性问题作了详尽的分析与探讨。  关键词 小产权房 法律分析 产权  中图分类号:D912.29文献标识码:A    一、前言    最近,深圳市通过了《关于农村城市化历史遗留违法建筑的处理决定》,使深圳市的小产权房市场又活跃起来,该规定被一些人认为是深圳市“小产权房”的准生证。“小产权房”从产生发展到今天,差不多已经10年了,尽管在这期间国土资
摘 要 本文主要对可供选择的两个会计确认基础进行了比较与分析,以期对初学者有所帮助。  关键词 会计确认 权责发生制 收付实现制   中图分类号:F231文献标识码:A    在会计理论和实务中,会计确认是一个十分重要的环节,它决定了会计核算主体何时将本单位具体的经济业务记录为何种要素,从而达到向信息使用者提供符合要求的会计信息这一根本目标。企业在持续经营过程中,不断地取得收入,也不断地发生费用,
分布式无线局域网技术近年来得到飞速的发展和广泛的应用,它具有通信快捷高效,组网迅速灵活等特点。因此,它也对传统的计算机网络技术作出必要的补充。如何在分布式环境下,使
本文概述了半导体器件模型的分类及近期发展,重点探讨了半导体模型中的Euler-Poisson方程组(也称经典的流体动力学模型)和一类带阻尼项的可压型Euler方程组在平衡态附近的扰动
本文通过对有限责任公司股东退出的原因、途径分析,结合我国现行立法状况及实际需要对股东退出机制进行完善.
曹策问教授对Sturm-liauville的谱问题进行了深入的研究,本文采用曹策问教授的方法研究了Dir‘算子的谱问题,得到了与S-L算子相平行的结论。本文在第二节中讨论Dir‘算子的’Le
广义逆在数值分析、数理统计、测量学和最优化等领域具有广泛重要的应用。尤其是在最小二乘问题,病态线性、非线性问题,不适定问题,回归、分布估计、马尔可夫链等统计问题,随机规
摘 要 本文通过分析知识产权行政保护与司法保护相比的特点,来界定行政保护与司法保护之间的关系,并展望二者未来的发展。  关键词 知识产权 行政保护 司法保护  中图分类号:DF523文献标识码:A    要了解知识产权行政保护的相关问题必须先从其概念入手。知识产权是指:公民或法人等主体依据法律的规定,对其从事智力创作或创新活动所产生的知识产品所享有的专有权利。知识产权有别于传统民事权利的特点使得对