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

【摘要】：圖G的一個(gè)k-無(wú)圈點(diǎn)染色是滿足任意兩種顏色類(lèi)的導(dǎo)出子圖是森林的G的一個(gè)k-正常點(diǎn)染色,G的無(wú)圈色數(shù)是使G存在無(wú)圈點(diǎn)染色最少的顏色數(shù),記為a(G).G的一個(gè)k-無(wú)圈全染色是滿足每一個(gè)圈上至少出現(xiàn)4種顏色的G的一個(gè)k-正常全染色,G的無(wú)圈全色數(shù)是使G存在無(wú)圈全染色最少的顏色數(shù),記為a_T(G).G的一個(gè)使用k種顏色的d-距離染色是滿足G中任意距離不超過(guò)d的兩頂點(diǎn)染不同的顏色的一個(gè)k-正常點(diǎn)染色,最少的顏色數(shù)稱為G的d-距離染色數(shù),記為χ_d(G).本文主要研究了兩個(gè)路的直積、半強(qiáng)積與強(qiáng)積以及字典積的無(wú)圈點(diǎn)染色,兩個(gè)路的笛卡爾積、直積、半強(qiáng)積與強(qiáng)積的無(wú)圈全染色,以及路與任意圖的字典積的d-距離染色,并利用構(gòu)造染色法與反證法得到了相應(yīng)染色數(shù).主要內(nèi)容包括以下三個(gè)部分.首先,得到了兩個(gè)路P_m和P_n的一些積的無(wú)圈點(diǎn)色數(shù),如直積P_m∧P_n、半強(qiáng)積P_m·P_n、強(qiáng)積P_m(?)P_n等.另外,給出了字典積P_m[H]的無(wú)圈點(diǎn)色數(shù),其中H是n階簡(jiǎn)單圖,且n,m≥2.其次,得到了兩個(gè)路P_m和P_n的一些積的無(wú)圈全色數(shù),如笛卡爾積P_m□P_n、直積P_m∧P_n、半強(qiáng)積P_m·P_n與強(qiáng)積P_m(?)P_n,其中n,m ≥ 2.最后,給出了路P_m與n階簡(jiǎ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 鈮，

本文編號(hào)：1626469