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

Jian-Ting Sheng ; Gui-Zhen Liu

Bulletin of the Malaysian Mathematical Society, Tome 34 (2011) no. 1

Résumé

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.

Détail

Classification : 05C15.