检索结果-南通市图书馆

检索条件"主题词=gc-染色"

共 1 条记录，以下是1-10 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

几乎正则图的f-色类与gc-色类的关系

几乎正则图的f-色类与gc-色类的关系

引用

作者：张蒙恩山东师范大学

学位级别：硕士

令C是一个颜色集.图G的边染色是颜色在图G的所有边上的一个分配.令G是一个图,一个图G的正常边染色是G的边染色使得G的每个点处不能有相同的颜色.一个图G的边覆盖染色是G的边染色使得每种颜色在每个点出至少出现一次.一个图G的f-染色和g... 详细信息

令C是一个颜色集.图G的边染色是颜色在图G的所有边上的一个分配.令G是一个图,一个图G的正常边染色是G的边染色使得G的每个点处不能有相同的颜色.一个图G的边覆盖染色是G的边染色使得每种颜色在每个点出至少出现一次.一个图G的f-染色和g-染色分别是正常边染色和边覆盖染色的推广.令f和g是两个函数,在每个点v ∈ V(G)处分别分配一个正整数f(v)和一个非负整数g(v). 一个图G的f-染色是G的边染色使得每个点v ∈ V(G)处最多有f(v)条边染相同的颜色.图G的g-染色是G的边染色使得每种颜色出现在每个点v ∈ V(G)处至少有g(v)次.清晰地,图G有g-边染色当且仅当对任意点v ∈V(G)有0 ≤ g(v)≤d(v).在这篇论文中,我们总是假设对任意点∈ V(G)有0≤g(v)≤d(v).将图G进行f-染色所需要的最小的颜色数目被称为图G的f-染色数,记作X’f(G).相对地,将图G进行g-染色所需要的最大的颜色数目被称为图G的g-染色数,记作X’g(G).当f= 1时,f-染色恰好是正常边染色;当g三1时,g-染色的确是边覆盖染色.因为正常边染色问题是NP-完备的(即使是对于立方图来说),所以f-染色问题和g-染色问题也是NP-完备的.1986年Hakimi和Kariv证明:任意简单图G有X’f(G)= △f(G)或△f(G) + 1,这里△f(G) = (?).如果X’f(G)= △f(G),称G为f-染色第一类图,否则称G为f-染色第二类图.这种确定简单图的f-染色数的问题称为f-染色的分类问题.宋慧敏和刘桂真在2005年给出的一个结果表明:任意简单图G有X’g(G)=δg(G)或δg(G) - 1,这里δg(G)=(?).如果X’g(G)=δg(G),称G为g-染色第一类图,否则称G为g-染色第二类图.这种确定简单图的g-染色数的问题称为g-染色的分类问题.本论文主要研究了几乎正则图的f-染色的分类问题以及f-色类与g-色类之间的关系,张霞2015年证明了对于任意的正则图G来说,当G的f-核与g-核是相同的,并且对于Jf-核或g-核里的每个点v都有f(v)=g (v),那么在f-色类与g-色类之间总是有一致性的结果.然而,对于其它的图(甚至是几乎正则图)来说,在f-色类与g-色类之间不是总是一致的.本论文对几乎正则图,当满足f-核与g-核是相同的,并且对任意f-核或g-核里的点v有f(v)=g(v)时,给出了f-色类与g-色类之间有一致性分类结果的一些充分条件.本文分为四章进行了讨论.在第一章中,介绍了研究背景以及研究意义,给出了本文中用到的基本概念与符号,给出了几类图的f-色类与g-色类的关系的研究现状和本文关于几乎正则图研究的主要结果;在第二章中,介绍了本文要用到的预备知识,包括主要的基本工具以及主要的引理;在第三章中,讨论了几乎正则图的f-色类与g-色类的关系,先给出了几乎正则图的f-染色分类的几个结论,然后给出f-核或g-核分别在r-度点集和r + 1-度点集内f-色类与g-色类关系的结论;在第四章中,给出了本论文可进一步研究的问题.

关键词：边染色边覆盖染色 f-染色 gc-染色图的分类几乎正则图

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

全选清除本页清除全部题录导出标记到“检索档案”

共1页 << < 1 > >>

回到顶部

执行限定条件

欢迎您,

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：