唯一顶点着色、唯一列表着色的整体结构与其着色参数的关系的讨论

来源 :首都师范大学 | 被引量 : 0次 | 上传用户:isc70279
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
这篇论文是一篇关于顶点着色综述性的文章。对图G(V,E)的一种着色是一个标号映射c:V→S,使得(?) vw∈E(G),c(v)≠c(w)。一个k-colouring是在顶点集V上的一个由k个色类构成的划分,使得在同一色类中的点不相邻。使得图G存在k-colouring c:V→{1,…,k}的最小的正整数k称为G的chromatic number,记为x(G)。如果图G的任何k-colouring产生的色类划分相同,我们称G是uniquely vertexk-colourable(or a k-UCG)。如果对图G的任何list assignment(?)={L(v):v∈V(G)}且|L(v)|=k,都能选择到G的着色。我们称G是k-list-colourable,或k-choosable,使得G是k-choosable最小的正整数k称为G的list chromatic number或choosability,记为ch(G)或x1(G)。第一章主要介绍了关于顶点着色的基本概念,一些着色参数的基本性质,简略地讨论了着色参数与图的结构的关系,最后一节是研究的进展和本文的主要结论。第二章找出例图使得ch(G)>x(G)或ch(G)=x(G),介绍了Woodall,Gravier和Maffray关于相等的猜测。给出了使得G是n-choosable的与kernel有关的充分条件,而且进一步指出线图是可解的当且仅当它是完美的,二部多重图的线图是可解的。第三章介绍了与n-choosable图不同的uniquely list colourable图的性质,主要介绍了uniquely 2-list colourable图的性质,一个连通图G是uniquely 2-list colourable当且仅当它至少有一块(block)既不是圈,不是完全图,也不是完全二部图。一个连通图G是uniquely2-list colourable当且仅当它至少有一块(block)既不是圈,不是完全图,也不是完全二部图。图G是uniquely 2-list colourable当且仅当它是t=max{3,x(G)}的uniquely(2,t)-listcolourable。在第四章的第一节,我们研究构造无Kk的k-UCG时,计算参数Λ(G)的值。首先找出具体的图说明无Kk的k-UCG的存在性,以此为基础用逼迫的办法构造k-UCG,而不增加团数,给出了计算Λ(G)的公式。在第二节用uniquely list colourable图(G,(?),t)与团K1构造t-UCG(?)G,φ,t,来计算固定集的最小值φ0(G),给出了xφ(G)与其它着色参数的不严格的不等式,而且计算出了圈Cn,路径Pn和彼得松图P的xφ(G)。
其他文献
温度是植物地理分布和生长的主要限制因素,低温寒害极大影响作物的品质和产量,世界上每年因此造成的损失高达2000亿美元。因此研究植物的冷耐受问题有重要的理论和实际意义。本实验以油菜素内酯受体突变体bril-5为实验材料,将生长14—21天的突变体和野生型放在零度以下的低温中黑暗处理发现突变体有更强的冷耐受性。在分别测定了突变体和野生型植株游离脯氨酸含量,可溶性糖含量,相对电导率,水含量,叶绿素含量后
历史研究是中日两国人文领域学术交流的重要组成部分。在中国古代史的研究中,日本学者是为数不多的、能够在史料占有与资料解读方面与中国本土学者进行较高水平交流的集体。翻译、介绍日本学者的学术论文等研究成果,能够为中国本土学者的研究锦上添花,助力“中国学”研究的完善与发展。奈达将翻译定义为“从语义到语体在译语中用最贴近而又最自然的对等语再现源语信息”,其中的“对等”要求译者通过调整译文词汇、句法结构、篇章
本篇翻译实践报告以《小偷》这一实践文本中出现的含有“~ている(ていた)”构式的句子为考察对象。依据“~ている”句的基础语法意义来分类案例,结合句子在文章中的语境,分析其表达功能。在功能对等理论的指导下,作出恰当的翻译,并从中找出其规律性内容,总结出“~ている”句在基础语法意义下的翻译策略,供今后的翻译者借鉴与参考。本篇实践报告首先介绍文本、选题、还有翻译过程的相关内容。在第二章中进行了文献综述,通
发展素质教育是中学物理教育的重要目标,新课标在2017年正式颁布并明确了高中教育的培养重心是着力发展核心素养,使学生具有科学文化素养和终身学习的能力。为了发展学生的核心素养,课堂教学是关键,采用怎样的教学设计能有效地促进学生核心素养的发展成为各研究者和一线教师重点关注的问题。本论文在了解各专家对提高核心素养的策略基础上,结合对一线教师调查发现教学设计中存在的问题,提出利用UbD(Understan
广西是我国甘蔗生产大省,据统计:2007-2016年,广西甘蔗年平均播种面积和总产量分比为105.8、7670.5万t,占全国的60.5%、64.7%,是全国甘蔗种植的主要产区[1]。由于特殊的地理环境,广西六成以上的甘蔗种植区都处在丘陵、坡地,种植面积小而分散,大型机械作业困难,使得甘蔗种植的整体机械化程度低,人工劳动强度大,种植成本高,严重制约了广西甘蔗业的发展。甘蔗转运车是重要的田间甘蔗搬运
一、引言近年来,国家大力推进全面依法治国,加强审计巡视检查,强化安全生产突出地位,外部监督检查日趋严格、方式日益多元、力度不断加大,对国网公司依法从严治企和确保安全生产提出了新的更高要求。国家审计署等政府部门将省管产业单位(集体企业)作为审计巡视重点,要求规范与主业关联交易,加快推进改革进程。国网公司总部严格对照国家有关政策法律法规和公司管理要求,结合近年内外部审计检查巡视发现的问题和社会关
会议
木质素是一种无定型三维网状芳香类高聚物,为自然界中唯一可再生的芳香化合物。对木质素进行定向催化氧化,可以得到芳香酮、醛、酸等物质,用作重要的化工中间体和平台分子。目前,对苯二甲酸作为工业生产聚对苯二甲酸丁二醇酯(PBT)、聚对苯二甲酸乙二醇酯(PET)的主要来源,主要通过氧化石油裂解得到的对二甲苯来获取。在石油煤炭资源紧张和环境污染高发的背景下,以木质素为原料制备芳香酸,具有绿色、可再生和价廉易得
教育改革在新课程标准的指导下有条不紊地进行着,人们对学生物理核心素养的研究也越来越多,物理核心素养包括四个方面:物理观念、科学思维、科学探究、科学态度与责任。科学探究是本次研究的主要关注点,广义的科学探究应该是:探究者通过自身主动参与、发现问题、解决问题的过程,科学探究应该体现在整个的学生的学习过程中。科学探究更是一种精神,是一种思维方式,一种研究手段。本次研究通过参照国际青年物理学家锦标赛(IY
随着城市化进程的推进,中国农村地区出现了大量的剩余劳动力,并在比较利益的带动下逐步转移到城镇。并逐步成为城市社会经济发展不可或缺的重要力量。但是,在城乡二元户籍制度下,大规模的农业移民人口在就业,子女教育,社会保障等方面不能享受与城镇居民相同的公共服务和社会福利,成为边缘化的弱势群体。如果从长远来看,这将成为中国城市化发展的潜在危机。尤其是近年来,农业转移的年轻一代人口普遍接受了高等教育,他们多数