Mycielskian图的全控制着色数

The Total Domination Chromatic Numbers of Mycielskian Graphs

摘要: 令图G=(V,E)是一个有限的简单的连通无向图。 图G的全控制着色是G的一个正常点着色，使得图G中每个顶点的开领域至少包含一种颜色类，且每个颜色类至少被一个顶点所控制。图G的全控制着色数是其全控制着色中所使用最少的颜色数，记为χ_td(G)。本文首先利用任意图G的全控制着色数给出了图G的 Mycielskian 图的全控制着色数的上、下界；进而给出了一些特殊图类的 Mycielskian 图的全控制着色数的确切值。

Abstract: Let G = (V,E) be a simple, connected, finite and undirected graph. A total domination coloring of a graph G is a proper coloring of G in which open neighbourhood of each vertex contains at least one color class and each color class is dominated by at least one vertex. The total domination chromatic number of G, denoted by χ_td(G), is the minimum number of colors required for a total domination coloring of G. In this paper, we present the upper and lower bounds of total domination chromatic numbers of Mycielskian graph of arbitrarily graph, and obtain exactly values of the total domination chromatic numbers of Mycielskian graphs of some special graphs.