[1,1,t]-Colorings of Complete Graphs |
| |
Authors: | Arnfried Kemnitz Massimiliano Marangio Zsolt Tuza |
| |
Affiliation: | 1. Computational Mathematics, Technische Universit?t Braunschweig, Pockelsstr. 14, 38106, Braunschweig, Germany 2. Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Reáltanoda u. 13–15, Budapest, 1053, Hungary 3. Department of Computer Science and Systems Technology, University of Pannonia, Egyetem u.?10, Veszprém, 8200, Hungary
|
| |
Abstract: | Given non-negative integers $r, s,$ and $t,$ an $[r,s,t]$ -coloring of a graph $G = (V(G),E(G))$ is a mapping $c$ from $V(G) cup E(G)$ to the color set ${1,ldots ,k}$ such that $left|c(v_i) - c(v_j)right| ge r$ for every two adjacent vertices $v_i,v_j, left|c({e_i}) - c(e_j)right| ge s$ for every two adjacent edges $e_i,e_j,$ and $left|c(v_i) - c(e_j)right| ge t$ for all pairs of incident vertices and edges, respectively. The $[r,s,t]$ -chromatic number $chi _{r,s,t}(G)$ of $G$ is defined to be the minimum $k$ such that $G$ admits an $[r,s,t]$ -coloring. In this note we examine $chi _{1,1,t}(K_p)$ for complete graphs $K_p.$ We prove, among others, that $chi _{1,1,t}(K_p)$ is equal to $p+t-2+min {p,t}$ whenever $t ge leftlfloor {frac{p}{2}}rightrfloor -1,$ but is strictly larger if $p$ is even and sufficiently large with respect to $t.$ Moreover, as $p rightarrow infty $ and $t=t(p),$ we asymptotically have $chi _{1,1,t}(K_p)=p+o(p)$ if and only if $t=o(p).$ |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|