检索结果-南通市图书馆

中国科学:数学 2024年

作者：张霞蒋真真张鑫淼山东师范大学数学与统计学院

设G是一个图,W是G的一些子图的集合.对G的一个m色的边染色,若与W中元素同构的子图上都出现了所有的m种颜色,则称该边染色是G的一个m色W-多色边染色.本文通过揭示图的子图多色边染色问题与Tur′an问题的密切联系,研究平衡完全二部图Kn,n... 详细信息

设G是一个图,W是G的一些子图的集合.对G的一个m色的边染色,若与W中元素同构的子图上都出现了所有的m种颜色,则称该边染色是G的一个m色W-多色边染色.本文通过揭示图的子图多色边染色问题与Tur′an问题的密切联系,研究平衡完全二部图Kn,n的W-子图多色边染色问题.当W是下列3种子图集合之一时:Hamilton圈、2-因子和Kn-1,n-1,本文确定Kn,n的W-子图多色数的值分别是n+1、n+1和■.此外,当主图是Kn,n时,本文证明任意一个2-因子的Tur′an数是n2-n+1.

关键词：多色染色多色子图 Tur′an数超图不交的横贯

来源：

同方期刊数据库评论

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

几类超图的多色染色问题研究

几类超图的多色染色问题研究

引用

作者：蒋真真山东师范大学

学位级别：硕士

超图H=(V(H),E(H))是由顶点集V(H)={v1,v2,...,vq}和超边集,E(H)={e1,e2,...,en}构成,其中ei(?)V(G),i={1,2,...,n}.令m是正整数,超图H是m-可染的是指用m种颜色对超图H的顶点进行染色使得H中没有单色超边.特别地,m=2时,称超图H是2-可染的(也称超图H有性质B).超图H的多色m-染色是指用m种颜色对H进行点染色使得每条超边包含每种颜色的至少一个点.使得超图H存在多色m-染色的最大值m被称为超图H的多色数.超图H的r-均衡多色染色是指H的一个多色染色使得每条超边包含每种颜色的至少r个点.超图的多色染色问题研究集中在两个方面,一是确定超图的多色数更好的上界或者下界,二是确定超图的r-均衡多色染色的存在性条件.首先,我们研究了几类超图的均衡多色染色.对于边数为n的超图,我们给出r-均衡多色数的几个下界.r是固定的正整数时,我们给出多色数的2ln n近似算法;r=O(ln(n ln n))时,给出一个O(ln n)近似算法;r=ω(ln(n ln n))时,给出一个(2+3)r近似算法.我们还给出了k-正则k-一致超图有均衡多色染色的充分条件.对于有差异的均衡多色染色,我们给出了超图有一个2-染色使得每条超边中一种颜色出现至少d1次另一种颜色出现至少d2次的充分条件.其次,我们讨论了图的子图多色边染色问题.目前这方面的研究集中在超立方体的子立方体多色边染色和完全图的因子多色边染色等几个方面.我们研究了完全二部图Kn,n的哈密顿圈子图多色边染色,并确定了其多色数为n+1.本论文共分四章进行讨论.第一章,我们主要介绍超图的多色染色问题的背景及重要意义,介绍论文中所涉及到的基本概念与符号,并且列出本文的主要结果.第二章,我们讨论超图的均衡多色染色问题,并证明超图的均衡多色数的三个下界.第三章,我们讨论完全二部图的子图多色边染色问题并证明Kn,n的哈密顿圈多色数为n+1.第四章,我们给出超图多色染色中可进一步研究的问题.

关键词：超图多色染色均衡染色多色子图概率方法

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：