本文選題：路　切入點：積圖　出處：《西北民族大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：圖G的一個k-無圈點染色是滿足任意兩種顏色類的導(dǎo)出子圖是森林的G的一個k-正常點染色,G的無圈色數(shù)是使G存在無圈點染色最少的顏色數(shù),記為a(G).G的一個k-無圈全染色是滿足每一個圈上至少出現(xiàn)4種顏色的G的一個k-正常全染色,G的無圈全色數(shù)是使G存在無圈全染色最少的顏色數(shù),記為a_T(G).G的一個使用k種顏色的d-距離染色是滿足G中任意距離不超過d的兩頂點染不同的顏色的一個k-正常點染色,最少的顏色數(shù)稱為G的d-距離染色數(shù),記為χ_d(G).本文主要研究了兩個路的直積、半強積與強積以及字典積的無圈點染色,兩個路的笛卡爾積、直積、半強積與強積的無圈全染色,以及路與任意圖的字典積的d-距離染色,并利用構(gòu)造染色法與反證法得到了相應(yīng)染色數(shù).主要內(nèi)容包括以下三個部分.首先,得到了兩個路P_m和P_n的一些積的無圈點色數(shù),如直積P_m∧P_n、半強積P_m·P_n、強積P_m(?)P_n等.另外,給出了字典積P_m[H]的無圈點色數(shù),其中H是n階簡單圖,且n,m≥2.其次,得到了兩個路P_m和P_n的一些積的無圈全色數(shù),如笛卡爾積P_m□P_n、直積P_m∧P_n、半強積P_m·P_n與強積P_m(?)P_n,其中n,m ≥ 2.最后,給出了路P_m與n階簡單圖H的字典積P_m[H]的d-距離色數(shù).
[Abstract]:A k-acyclic point coloring of a graph G is a derived subgraph satisfying any two classes of colors. The acyclic chromatic number of a k-normal point coloring G of a forest is the least number of colors in which G has an acyclic point coloring. A k- acyclic total coloring, denoted as a G, is a k- normal total chromatic number of G which satisfies at least four colors on each cycle. It is the least number of colors in which G exists in acyclic total coloring. A d- distance coloring with k colors, denoted as a _ T _ T _ G, is a k- normal point coloring of different colors satisfying two vertices of G with any distance of not more than d, and the minimum number of colors is called the number of d- distance coloring of G, In this paper, we study the direct product of two paths, semi-strong product and strong product, acyclic point coloring of dictionary product, Cartesian product, direct product, semi-strong product and acyclic total coloring of two paths. And the D-distance coloring of dictionary product of path and arbitrary graph, and the corresponding coloring number is obtained by means of constructive staining method and counter-proof method. The main contents include the following three parts. First, the acyclic point chromatic number of some products of two paths PSP _ m and P _ n are obtained. For example, direct product P\ + m\\\%\\\'\\\}\\. In addition, the acyclic point chromatic number of the dictionary product PIM [H] is given, where H is a simple graph of order n and NM 鈮，

本文編號：1626469