论文题目: 图的点荫度和点线性荫度
论文类型: 博士论文
论文专业: Operations,Research,&,Cybernetics
作者: 左连翠
导师: 刘家壮
关键词: 点荫度,点线性荫度,树染色,路染色,距离图,整数距离图,距离集,分数路染色,分数点线性荫度
文献来源: 山东大学
发表年度: 2005
论文摘要: 图的点染色理论一直是图论界的一个热门话题。一个图G的一个k-着色是从V（G）到{1,2,…,k}的一个映射,对于图G的一个给定的k-着色,Vi表示G中染i色的所有顶点,而G[Vi]表示Vi在G中的点导出子图。若Vi（1≤i≤k）都是独立集,则称f是一个正常k-着色。使得图G有正常k-着色的最小数k称为G的点色数,记为x（G）。若有x（G）=k,则称G是k-色图。若对于G的任意真子图H,都有x（H）<x（G）,则称G是临界图。一个k-临界图是一个k-色的且临界的图;任何k-色图都有一个k-临界子图。 在一个k-着色中,若G[Vi]（1≤i≤k）的每个连通分支都是树,则称f是一个树k-着色。使得图G有树k-着色的最小正整数k称为G的点荫度,记为va（G）。 Kronk等人证明了对于任意图G,有va（G）≤[（△（G）+1）/2]。Catlin等人证明了非圈非完全的图G的点荫度va（G）≤[（△（G））/2]。（?）krekovski证明了局部平面图的点荫度≤3,而无三角形的局部平面图的点荫度≤2。G.Chartrand等人证明了任意平面图的点荫度≤3,以及n-部完全图K（p1,p2,…,pn）（1≤p1≤p2≤…≤pn）的点荫度是n-max{k|sum from 0 to k pi≤n-k},其中p0=0。后来有许多人,如N.Alon等,也研究了图的点荫度。 若G[Vi]（1≤i≤k）的每个连通分支都是路,则称f是一个路k-着色。使得图G有路k-着色的最小正整数k称为G的点线性荫度,记为vla（G）。显然,对于任意的图G,有va（G）≤vla（G）≤x（G）。 Matsumoto证明了:对于有限图G,vla（G）≤[（△（G）+1）/2],进而,若△（G）为偶数,则vla（G）=[（△（G）+1）/2]当且仅当G为△（G）+1阶的完全图或为一个圈;Goddard和Poh证明了对于平面图G,有vla（G）≤3;Akiyama证明了对于外平面图G,有vla（G）≤2。Alavi等人证明了对于任意阶为n的图G,有vla（G）+vla（（?））≤1+[（n+1）/2],其中（?）是G的补图。 给定任一正实数集D,令G（R,D）表示实数轴上的所有点作为点集合,而两个
论文目录:
Chinese abstract
English abstract
Notation index
Chapter 1. Introduction
1.1 Basic concepts
1.2 The development of the vertex arboricity and the vertex linear arboricity of graphs
1.3 Main results
Chapter 2. The vertex arboricity of distance graphs
2.1 The distance graph which distance set is an interval
2.2 The integer distance graphs with general distance sets
2.3 The vertex arboricity of integer distance graphs G(D_(m,k,1))
2.4 The vertex arboricity of integer distance graphs G(D_(m,k,2))
2.5 The vertex arboricity of integer distance graphs G(D_(m,1,3))
Chapter 3. The Vertex Linear Arboricity of the Distance Graphs
3.1 The vertex linear arboricity of the real distance graphs
3.2 The vertex linear arboricity of integer distance graphs
3.3 The vertex linear arboricity of integer distance graphs G(D_(m,k,1))
3.4 The vertex linear arboricity of integer distance graphs G(D_(m,k,2))
3.5 The vertex linear arboricity of integer distance graphs G(D_(m,k,3))
Chapter 4. The Fractional Vertex Linear Arboricity of Graphs
4.1 Introduction
4.2 The fractional vertex linear aboricity of graphs
Bibliography
Acknowledgements
Curriculum Vitae
学位论文评阅及答辩情况表
发布时间: 2005-10-17
参考文献
- [1].关于图的一些荫度问题的研究[D]. 陶昉昀.东南大学2015
- [2].图的广义着色[D]. 杨爱峰.郑州大学2004
- [3].平面图的邻点可区别染色与点荫度[D]. 黄丹君.苏州大学2012
- [4].平面图的若干染色问题[D]. 蔡华.山东大学2016
- [5].图的边染色及一些有限制条件的染色[D]. 高毓平.山东大学2016
相关论文
- [1].图的广义着色[D]. 杨爱峰.郑州大学2004
- [2].图的交叉数等图论难题的研究[D]. 林晓惠.大连理工大学2004
- [3].图的限制染色及其相关问题的研究[D]. 赵永强.河北师范大学2005
- [4].图的控制数及其相关参数[D]. 单而芳.上海大学2005
- [5].关于图的因子与分数因子的若干结果[D]. 卞秋菊.山东大学2005
- [6].拟阵与图[D]. 李乐学.山东大学2005
- [7].线图与若干典型图类的交叉数研究[D]. 赵霆雷.湖南师范大学2006
- [8].关于图的可选择性与唯一列表可染图研究[D]. 申玉发.河北师范大学2006
- [9].图的边覆盖染色及分数边染色[D]. 王纪辉.山东大学2006
- [10].图的因子和分数因子[D]. 蔡建生.山东大学2007
标签：点荫度论文; 点线性荫度论文; 树染色论文; 路染色论文; 距离图论文; 整数距离图论文; 距离集论文; 分数路染色论文; 分数点线性荫度论文;