Volume 34 • Number 1 • 2011   • A Note on \([r, s, c, t]\)-Colorings of Graphs Jian-Ting Sheng and Gui-Zhen Liu Abstract. Let \(G\) be a simple graph with vertex set \(V(G)\) and edge set \(E(G)\). A subset \(S\) of \(V(G)\) is called an independent set if no two vertices of \(S\) are adjacent in \(G\). The minimum number of independent sets which form a partition of \(V(G)\) is called chromatic number of \(G\), denoted by \(\chi(G)\). 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 \(G\), denoted by \(\chi'_{c}(G)\). Given nonnegative integers \(r, s, t\) and \(c\), an \([r, s,c,t]\)-coloring of \(G\) is a mapping \(f\) from \(V(G)\bigcup E(G)\) to the color set \(\{0,1,\ldots,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 \(|f(v_i)-f(v_j)|\geq r\) if \(v_i\) and \(v_j\) are adjacent, \(|f(e_i)-f(e_j)|\geq s\) for every \(e_i, e_j\) from different edge covers, \(|f(v_i)-f(e_j)|\geq 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 \(\chi_{r,s,c,t}(G)\) of \(G\) is defined to be the minimum \(k\) such that \(G\) admits an \([r,s,c,t]\)-coloring. In this paper, we present the exact value of \(\chi_{r,s,c,t}(G)\) when \(\delta(G)=1\) or \(G\) is an even cycle. 2010 Mathematics Subject Classification: 05C15. Full text: PDF