几类图的线性荫度和线性K-荫度

摘要

图的着色理论和分解理论在许多领域都有很重要的应用。图的线性荫度和线性k-荫度是图的着色理论和分解理论中两个重要的概念，近三十年来在国内外得到了广泛的研究。一个图G的线性k-森林是图G的一个子图，其中，它的每个连通分支为长度最多为k的路。图G的线性k-荫度lak(G)即为分解图G的边集E(G)所需要的线性k-森林的最小数目。图G的线性k-荫度的概念最早是由Habib和Peroche提出的，它是边染色的自然推广。显然，一个线性1-森林就是一个匹配，la1(G)就是图G的边色数，也即x'(G)。当森林的每条路的长度没有限制时，则图G的边集E(G)分解成这种森林的最小数目就是图G的线性荫度，记作la(G)或者la∞(G)。下面关于lak(G)的上界的猜想1.1是由Habib和Peroche在1982年提出的。猜想1.1lak(G)≤{「△(G)|V(G)|/2([)k|V(G)/k+1」(])，若△(G)=|V(G)|-1，「△(G)|V(G)|+1/2([)k|V(G)|/k+1」，若△(G）＜| V(G)|-1，当k=|V(G)|-1时，这就是Akiyama的猜想。
　　本研究分为五个部分：第一章介绍了预备知识和图的线性荫度和线性k-荫度的相关研究背景。第二章得到了m个圈Cnt的笛卡尔积图Cmnt的线性(n-1)-荫度的精确值。第三章得到了完全图Kn和均衡完全二部图Kn，n的笛卡尔积图Kn□Kn，n的线性(n-1)-荫度。第四章讨论了完全图Kn的Mycielski图M（Kn）的线性k-荫度，并得到了精确值。第五章讨论了完全二部图Km,n的线性6-荫度，进而研究了完全二部图Km，n的线性t-荫度并得到了精确值。

目录

声明

摘要

Abstract

Chapter 1 Introduction

§1．1 Preliminaries

§1．2 Studying background

Chapter 2 The linear(n-1)-arboricity of Cartesian product graph Cmnt

chapter 3 The linear(n-1)-arboricity of Cartesian product graph Kn□Kn，n

Chapter 4 The linear arboricity and linear k-arboricity of Mycielski graph M(Kn)

Chapter 5 The linear 6-and t-arboricity of Km，n

§5．1 The linear 6-arboricity of Km，n

§5．2 The linear t-arboricity of Km，n

参考文献

研究生期间已发表论文

致谢