A Note on [r, s, c, t]-Colorings of Graphs

作者：Sheng Jian Ting^*; Liu Gui Zhen

来源：Bulletin of the Malaysian Mathematical Sciences Society, 2011, 34(1): 165-169.

• [r, s, c, t]-coloring
• edge covering coloring
• chromatic number
• [r, s, t}-coloring

Let G be a simple graph with vertex set V(C) and edge set E(C). A subset S of V(C) is called an independent set if no two vertices of S are adjacent in C. The minimum number of independent sets which form a partition of 11(C) is called chromatic number of C, denoted by x(C). A subset S of E(G) is called an edge cover of G if the subgraph induced by S is a spanning subgraph of G. The maximum number of edge covers which form a partition of E(G) is called edge covering chromatic number of C, denoted by x'(c)(G). Given nonnegative integers r, s, t and c, an [r, s, c, t]-coloring of C is a mapping f from V (G)U E(G) to the color set {0, 1, ...,k - 1} such that the vertices with the same color form an independent set of G, the edges with the same color form an edge cover of G, and vertical bar f (v(i)) - f (v(j))vertical bar >= r if v(i) and v(j) are adjacent, vertical bar f (e(i)) - f(e(j))vertical bar >= s for every ej from different edge covers,vertical bar f(v(i)) - f(e(j))vertical bar >= t for all pairs of incident vertices and edges, respectively, and the number of edge covers formed by the coloring of edges is exactly c. The [r, s, c, t]-chromatic number Xr,s,c,t(G) of G is defined to be the minimum k such that G admits an [r, a, c, t]-coloring. In this paper, we present the exact value of xr,s,c,t(G) when delta(G) = 1 or G is an even cycle.

• 出版日期2011
• 单位山东大学