路的积图的无圈点（全）染色与距离染色

发布时间：2018-03-17 21:04

  本文选题：路　切入点：积图　出处：《西北民族大学》2017年硕士论文　论文类型：学位论文

【摘要】：图G的一个k-无圈点染色是满足任意两种颜色类的导出子图是森林的G的一个k-正常点染色,G的无圈色数是使G存在无圈点染色最少的颜色数,记为a(G).G的一个k-无圈全染色是满足每一个圈上至少出现4种颜色的G的一个k-正常全染色,G的无圈全色数是使G存在无圈全染色最少的颜色数,记为a_T(G).G的一个使用k种颜色的d-距离染色是满足G中任意距离不超过d的两顶点染不同的颜色的一个k-正常点染色,最少的颜色数称为G的d-距离染色数,记为χ_d(G).本文主要研究了两个路的直积、半强积与强积以及字典积的无圈点染色,两个路的笛卡尔积、直积、半强积与强积的无圈全染色,以及路与任意图的字典积的d-距离染色,并利用构造染色法与反证法得到了相应染色数.主要内容包括以下三个部分.首先,得到了两个路P_m和P_n的一些积的无圈点色数,如直积P_m∧P_n、半强积P_m·P_n、强积P_m(?)P_n等.另外,给出了字典积P_m[H]的无圈点色数,其中H是n阶简单图,且n,m≥2.其次,得到了两个路P_m和P_n的一些积的无圈全色数,如笛卡尔积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-距离色数.
[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