發(fā)布時間：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

【參考文獻】

相關期刊論文 前4條

1 Hua Wen MA;Xia ZHANG;;Some Class 1 Graphs on g_c-colorings[J];Acta Mathematica Sinica;2016年10期

2 Xia ZHANG;Gui Ying YAN;Jian Sheng CAI;;f-Class Two Graphs Whose f-Cores Have Maximum Degree Two[J];Acta Mathematica Sinica(English Series);2014年04期

3 宋慧敏,劉桂真;圖的f-邊覆蓋染色[J];數學學報;2005年05期

4 宋慧敏,劉桂真;ON f-EDGE COVER-COLOURING OF SIMPLE GRAPHS[J];Acta Mathematica Scientia;2005年01期

，

本文編號：2038022