关于图的可选择性与唯一列表可染图研究

来源 :河北师范大学 | 被引量 : 0次 | 上传用户:jiachengpu
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文研究列表染色的若干问题,包括图的色-可选择性和Ohba猜想、某些平面图的(k,l)-可选择性和(k,l)-边-可选择性,以及图(尤其是完全多部图)的唯一列表可染性. 如果图G满足Ch(G)=χ(G),则称G是色-可选择的.关于图的色-可选择性,2002年Ohba[71]给出猜想:如果图G满足|V(G)|≤2χ(G)+1,则G是色-可选择的.容易发现Ohba猜想成立当且仅当其对完全多部图成立,但是对完全多部图Ohba猜想被验证的情况只有图K3*2,2*(k-3),1、K3,2*(k-1)和Kt+3,2*(k-t-1),1*t·本文证明:完全多部图Kt+2,3,2*(k-t-2),1*t(t=2,3,4;k≥t+2)是色-可选择图.因此得到,对图Kt+2,3,2*(k-t-2),1*t(t=1,2,3,4;k≥t+2)及其所有k-色子图Ohba猜想成立.对独立数最大为3的图,2004年Ohba[72]证明了Ohba猜想的一个较弱的形式:如果图G满足|V(G)|≤2χ(G),且G的独立数最大为3,则G是色-可选择的.在此我们证明:若r≤t+1且k≥r+t,则Ch(K3*r,2*(k-r-t),1*t)=χ(K3*r,2*(k-r-t),1*t)=k.此结果表明:在如上Ohba的论断中,条件|V(G)|≤2χ(G)可以换成|V(G)|≤2χ(G)+1.即对每个独立数最大为3的图及其所有χ(G)-色子图Ohba猜想成立. 图的(k,l)-可选择性问题是图的k-可选择性问题的推广.关于图的(k,l)-可选择性,1979年Erdos等人[26]提出了如下猜想:对任意整数m≥1,每一个(k,l)-可选择的图G也是(km,lm)-可选择的.1996年Tuza和Voigt[94]证明了这个猜想在k=2和l=1的情形是正确的,但是对任意的(k,l)验证这个猜想的工作还相差甚远.本文证明:对任意整数m≥1,每一个没有t-圈(t=3,4,5或6)的平面图是(4m,m)-可选择的.这一结果推广了分别由Lam等人[65]、由Wang和Lih[106]、由Fijavz等人[28]给出的如上图都是4-可选择的结果.另一方面,我们还证明:如果一个平面图G不包含t-圈(t=3,4,5或6)且△(G)≠4,则对任意整数m≥1,G是(sm,m)-边-可选择的,这里当t∈{3,4,5},或t=6但△(G)≠5时,s=△(G)+1;当t=6且△(G)=5时,s=7.除了△(G)=4以及t=6且△(G)=5的情况之外,该结果推广了分别由Wang和Lih[105,106]、Zhang和Wu[114]、王维凡[117]给出的不包含t-圈(t=3,4,5或6)的平面图都是(△(G)+1)-边-可选择的结果.此外,作为我们主要结果的推论得到:每一个没有4-圈的平面图G都是(△(G)十1)-边-可选择的.该结果也改进了Zhang和Wu给出的结果:如果图G是没有4-圈的平面图,则G是s-边-可选择的,这里当△(G)≠5时,s=△(G)+1;当△(G)=5时,s=7. 如果图G存在一个k-列表安排L,使得G有唯一的一个L-染色,则称G是唯一k-列表可染的,简称G是UkLC图.1999年Mahdian和Mahmoodian[67]特征化了U2LC图.2001年Ghebleh和Mahmoodian[32]深入地研究了完全多部图的唯一列表可染性,尤其是唯一3-列表可染性,除去9个完全多部图不能确定之外,他们特征化了U3LC完全多部图.与此同时,针对这9个被剔除的图,他们提出了如下开放问题:查证图K2,2,r,r=4,5,…,8,K2,3,4,K1*4,4,K1*4,5和K1*5,4不是U3LC图.2004年Zhao等人[115]证明了图K2,3,4不是U3LC图.本文首先研究U2LC图特征化定理证明的简化问题.然后证明:图K2,2,r,r=4,5,…,8,K1*4,4,K1*4,5和K1*5,4都不是U3LC图.因此,唯一3-列表可染的完全多部图得到全面特征化.
其他文献
在西气东输二线输气站场中,24V供电及信号回路的绝缘性能无法实时在线监测。为解决该问题,研究了以现有的监控和数据采集系统为基础的绝缘监测系统,详细阐述了该系统的工作原
有机化学是高中化学中一个重要的组成部分,在高考当中比重较大,因其种类繁多、结构复杂,不仅是学生学习中的重点、难点,也是教师教学中的难点内容之一.教师必须根据有机化学
学位
本文作者介绍了建筑工程中混凝土的施工方法,阐述了建筑工程中混凝土施工的要点,最后探讨了建筑工程中混凝土施工技术的强化措施。
  本文应用间断有限元方法对一系列的高阶导数非线性波动方程进行研究,这些非线性方程包括一维标量方程、一维方程组和二维标量方程,涉及到KdV-Burgers方程、Kuramoto-Siv
本文讨论了两类具有边界条件的非线性波动方程。在适当的初值条件下得到了这两类方程解的存在唯一性及相应能量的衰减性质。 第一章简单说明了研究这两类偏微分方程的重要
本文主要以李群、辛流形及群胚等为基本研究对象。抓住李群同时是群和微分流形的特殊性质,将辛结构和仿射群在李群上进行了推广,并讨论了它们的一些相关性质。最后在特殊纤维丛
本文作者介绍了带钢桁架转换层高层建设结构体系的构造要求,通过对工程实例的分析,研究了结构选型的确定等方面,供同行参考。
本文作者分析阐述了在大体积混凝土浇筑过程中的若干注意事项,供大家参考借鉴。
本文结合高层建筑结构设计实例,对连体结构设计技术进行了研究,分别介绍了结构选型、连接方式选择、抗震受力特性、支座设计方法。