平面图的injective列表染色

论文摘要

本文仅考虑有限简单图.对于一个平面图G,顶点集、边集、最大度、最小度、面集、围长及G中两点u,v间的距离分别记作V（G）,E（G）,△（G）,δ（G）,F（G）,g（G）和dG（u,v）.图G的一个injective k-染色,指的是一个映射φ:V（G）→{1,2,...,k},使得有公共邻点的2个顶点u,v满足φ（u）≠φ（v）.若图G有一个injective k-染色,则称图G是injective k-可染的,并称χi（G）=min{k|G是injective k-可染的}为G的injective-染色数.图G的一个列表配置L是指对每个顶点v∈V分配一个可用色集L（v）.对G的一个列表配置L,若G的一个injective-染色φ,满足φ（v）∈L（v）（（?）v∈V（G））,则称φ是G的一个injective L-染色.图的染色理论是图论中重要的领域,随着应用科学不断发展,图的染色种类日益增加,譬如列表染色、线性染色、边可区别染色、星染色等等.早在本世纪初,学者Hahn等人提出了一种新的染色injective-染色.Injective-染色未必是非正常染色.学者Kim与Oum等人给出以下定理:对任意一个简单图H,均有χi（H）≤ χ（H2）≤ 2χi（H）.该定理非常直观的反映了图的injective-染色问题与平方图的染色问题的关系.本学位论文主要研究了平面图的injective-列表染色的一些结论.在第二章中,研究了围长至少为5且△（G）≥ 11的平面图G,有χil（G）≤ △（G）+4.在第三章中,研究了 5--圈与5--圈不交且△（G）≥ 18的平面图G,有χil（G）<△（G）+6.

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 基本概念
•   1.2 Injective-染色的研究现状
•   1.3 主要结果
• 第二章 围长至少为5的平面图的injective-列表染色
• -—圈和5^-—圈不交的平面图的injective-列表染色'>第三章 5^-—圈和5^-—圈不交的平面图的injective-列表染色
• 参考文献
• 功读学位期间取得的研究成果
• 致谢

文章来源

类型: 硕士论文

作者: 黄超媛

导师: 卜月华

关键词: 染色,围长,平面图,最大度

来源: 浙江师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 浙江师范大学

分类号: O157.5

DOI: 10.27464/d.cnki.gzsfu.2019.000778

总页数: 52

文件大小: 2591K

下载量: 9