Authors: Arnfried Kemnitz Massimiliano Marangio Zsolt Tuza
Publish Date: 2012/03/20
Volume: 29, Issue: 4, Pages: 1041-1050
Abstract
Given nonnegative integers r s and t an rstcoloring of a graph G = VGEG is a mapping c from VG cup EG to the color set 1ldots k such that leftcv i cv jright ge r for every two adjacent vertices v iv j leftce i ce jright ge s for every two adjacent edges e ie j and leftcv i ce jright ge t for all pairs of incident vertices and edges respectively The rstchromatic number chi rstG of G is defined to be the minimum k such that G admits an rstcoloring In this note we examine chi 11tK p for complete graphs K p We prove among others that chi 11tK p is equal to p+t2+min pt whenever t ge leftlfloor fracp2rightrfloor 1 but is strictly larger if p is even and sufficiently large with respect to t Moreover as p rightarrow infty and t=tp we asymptotically have chi 11tK p=p+op if and only if t=op
Keywords: