【作者】 王纪辉；

【导师】 刘桂真；

【作者基本信息】 山东大学 ， 运筹学与控制论， 2006， 博士

【摘要】 图的染色理论是图论中的一个重要分支。图的染色种类有很多，诸如边染色、点染色、面染色和全染色等。其中研究最多，结果也较完善的就是图的边染色。图的正常的边染色就是把图的边集分解为一些互不相交的边的独立集的并的方法。在图的正常边染色理论中有著名的Vizing定理，而其中关于正常边染色的图的分类问题一直是研究的热点。近年来，人们开始考虑把图的边集分解为其它形式，得到一些推广的边染色并进行研究。本文主要是讨论了图的边覆盖染色、f-边覆盖染色、分数边覆盖染色和分数边染色等。 我们用G（V，E）表示一个图，其中V是顶点集，E是边集。设S是一个集合，|S|表示集合S的基数。在本文中我们所说的图通常指有限简单图。如果图G中允许有重边则称G为重图。对图G中的点v，用d_G（v）表示顶点v的度，用N_G（v）表示v的邻点集。记δ（G）=min{d_G（v）：v∈V（G）}。△（G）=max{d_G（v）：v∈V（G）}，则δ（G）和△（G）分别表示图G的最小度和最大度。在不产生混淆的情况下，我们常用V，E，N（v），δ，△分别代替V（G），E（G），N_G（v），δ（G），△（G）。 令G_δ表示图G中由最小度点导出的子图。如果△（G）=δ（G）=d则称G是d-正则图，通常也称3-正则图为立方图。如果图G的顶点集可以划分为两个互不相交的子集V₁和V₂且G的任何一条边的两个端点分别在V₁和V₂中，则称图G为二部图。若图G中存在一点u使得G-u是一个具有二划分为（X，Y）的二部图则称G为近似二部图，记为G（X，Y；u）。一个圈是指图中每个点的度都是2的连通图，称含有奇数条边的圈为奇圈，含有偶数条边的圈为偶圈。 我们用正整数1，2，…来表示颜色，若C是边集E到集合{1，2，…，k}的映射，即C：E→{1，2，…，k}，则称C为图G的k-边染色。令C_i（v）表示在图G的在染色C中与顶点v关联的染i色边的数目。假定对V中每个顶点v都已赋以正整数f（v）且要求1≤f（v）≤d（v）。若染色C使图G中任意顶点v∈V和i∈{1，2，…，k}，都有C_i（v）≥f（v）成立，则称C为图G的f-边覆盖更多还原

【Abstract】 The coloring theory of graphs is one important branch of graph theory. The coloring theory has many kinds, such as edge coloring, vertex coloring, face coloring, total coloring and so on. Among them, the edge coloring is given most attention and has many perfect results. The proper edge coloring is to divide the edge set of G into some dijoint independent edge sets. In proper edge coloring theory, it is well known that Vizing’s Theorem and the classification problem. Recently, many authors consider the generalization of proper edge coloring, that is, we can consider other forms in which we can divide the edge set. The aim of this thesis is to discuss some topics on edge coloring problems such as edge cover coloring, f-edge cover coloring, fractional edge cover cloring and fractional edge coloring of graphs.Let G（V, E） be a graph with vertex set V and edge set E. If 5 is a set, we shall denote by \S\ the cardinality of 5. Throughout this thesis the term graph is used to denote a simple graph G with finite vertex set V and a finite edge set E. If multiple edges are allowed, G is called a multigraph. For a vertex v of G, the degree of v in G is denoted by d_c（v）. Let N_G（v） denote the set of neighbors of vertex v. Set δ（G） = min{d_G（v） : v （?） V（G）}, the minimum degree of G, and △（G） = max{d_G{v) : v （?） V（G）}, the maximum degree of G. If there is no confusion, we use V, E, N（v）, δ, A instead of V（G）, E（G）, N_G（v）, δ（G）, A（G）, respectively.Let G_δ denote the subgraph of G induced by the vertices of degree S. G is regular if △（G） = δ（G） = d, we also say that G is d-regular. A graph is cubic if it is 3-regular. A graph G is bipartite if there exists a partition （V₁. V₂） of V（G）更多还原