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

发布时间：2018-06-19 02:43

本文选题：边染色 + 边覆盖染色　；参考：《山东师范大学》2017年硕士论文

【摘要】：令C是一个颜色集.图G的边染色是颜色在图G的所有边上的一个分配.令G是一个图,一个图G的正常边染色是G的边染色使得G的每个点处不能有相同的颜色.一个图G的边覆盖染色是G的边染色使得每种颜色在每个点出至少出现一次.一个图G的f-染色和g_c-染色分别是正常边染色和边覆盖染色的推广.令f和g是两个函数,在每个点v ∈ V(G)处分别分配一个正整数f(v)和一个非负整数g(v). 一个图G的f-染色是G的边染色使得每个点v ∈ V(G)处最多有f(v)条边染相同的颜色.图G的g_c-染色是G的边染色使得每种颜色出现在每个点v ∈ V(G)处至少有g(v)次.清晰地,图G有g_c-边染色当且仅当对任意点v ∈V(G)有0 ≤ g(v)≤d(v).在这篇论文中,我们总是假设对任意点∈ V(G)有0≤g(v)≤d(v).将图G进行f-染色所需要的最小的颜色数目被称为图G的f-染色数,记作X'f(G).相对地,将图G进行g_c-染色所需要的最大的颜色数目被称为图G的g_c-染色数,记作X'g_c(G).当f= 1时,f-染色恰好是正常边染色;当g三1时,g_c-染色的确是边覆盖染色.因为正常边染色问题是NP-完备的(即使是对于立方图来说),所以f-染色问题和g_c-染色问题也是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_c(G)=δg(G)或δg(G) - 1,这里δg(G)=(?).如果X'g_c(G)=δg(G),称G为g_c-染色第一类图,否则称G为g_c-染色第二类图.这种确定简单图的g_c-染色数的问题称为g_c-染色的分类问题.本论文主要研究了几乎正则图的f-染色的分类问题以及f-色类与g_c-色类之间的关系,张霞2015年证明了对于任意的正则图G来说,当G的f-核与g_c-核是相同的,并且对于Jf-核或g_c-核里的每个点v都有f(v)=g (v),那么在f-色类与g_c-色类之间总是有一致性的结果.然而,对于其它的图(甚至是几乎正则图)来说,在f-色类与g_c-色类之间不是总是一致的.本论文对几乎正则图,当满足f-核与g_c-核是相同的,并且对任意f-核或g_c-核里的点v有f(v)=g(v)时,给出了f-色类与g_c-色类之间有一致性分类结果的一些充分条件.本文分为四章进行了讨论.在第一章中,介绍了研究背景以及研究意义,给出了本文中用到的基本概念与符号,给出了几类图的f-色类与g_c-色类的关系的研究现状和本文关于几乎正则图研究的主要结果;在第二章中,介绍了本文要用到的预备知识,包括主要的基本工具以及主要的引理;在第三章中,讨论了几乎正则图的f-色类与g_c-色类的关系,先给出了几乎正则图的f-染色分类的几个结论,然后给出f-核或g_c-核分别在r-度点集和r + 1-度点集内f-色类与g_c-色类关系的结论;在第四章中,给出了本论文可进一步研究的问题.
[Abstract]:C is a color set. The edge coloring of graph G is a distribution on all sides of the graph G. Order G is a graph, the normal edge coloring of a graph G is the edge coloring of G so that every point in G can not have the same color. A graph G edge coloring is the edge coloring of G so that each color appears at least once at each point. A graph. The f- and g_c- coloring of G are the extension of normal edge coloring and side cover dyeing respectively. F and G are two functions. A positive integer f (V) and a non negative integer g (V) are allocated at each point v V (G). Coloring is the edge coloring of G so that each color appears at at least g (V) at each point, V, V (G). Clearly, the graph G has g_c- edge coloring if and only if the V V (G) of any point is 0 < < < g >. The number of f- coloring known as graph G is recorded as X'f (G). Relative, the maximum number of colors required for g_c- dyeing of figure G is called g_c- dyeing number of figure G, which is recorded as X'g_c (G). When f= 1, f- dyeing happens to be a normal edge coloring; when the three 1 is 1, the dyeing is certainly edge coloring. Even if the normal edge dyeing problem is complete (even if it is For the cubic graph, the f- dyeing problem and the g_c- dyeing problem are also NP- complete.1986 years Hakimi and Kariv proof that any simple graph G has X'f (G) = delta f (G) or delta f (?) + 1. The problem is called the classification problem of f- dyeing. A result given by Song Huimin and Liu Guizhen in 2005 shows that any simple graph G has X'g_c (G) = [delta] g (G) or delta G (G) - 1, here delta G (G) = (?). If X'g_c (G) = delta is considered as the first class diagram of dyeing, otherwise the problem of determining the number of dyes for a simple graph is called. This paper is called the classification problem of g_c- dyeing. In this paper, we mainly study the classification of f- coloring of almost regular graphs and the relationship between f- color class and g_c- color class. In 2015, Zhang Xia proved that for any regular graph G, when G's f- kernel is the same as g_c- kernel, and for Jf- kernel or g_c- kernel, every point v has f. There is always consistency between the f- color class and the g_c- color class. However, for other graphs (even almost regular graphs), both the f- color class and the g_c- color class are not always consistent. In this paper, the almost regular graph, when the f- kernel is the same as the g_c- kernel, and a f (V) =g (V) =g (V) =g (V) for the point v in the f- kernel or g_c- kernel. There are some sufficient conditions for the consistency classification between color class and g_c- color class. This paper is divided into four chapters. In the first chapter, the background and significance of the research are introduced. The basic concepts and symbols used in this paper are given. The research status of the relationship between f- color classes and g_c- color classes of several classes of graphs is given and the article is about almost the same. In the second chapter, we introduce the preparatory knowledge used in the second chapter, including the main basic tools and the main lemmas. In the third chapter, the relationship between the f- color classes of almost regular graphs and the g_c- color classes is discussed. First, several conclusions of the f- dyed classification of almost regular graphs are given, and then the f- kernel or g_c- kernel is given. The conclusion of the relationship between f- chromatic class and g_c- color class in r- degree set and R + 1- degree set is given respectively. In the fourth chapter, the problems that can be further studied in this paper are given.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】