On t-relaxed chromatic number of r-power paths
Jun Lan, Wensong Lin · Discrete Mathematics Algorithms and Applications · 2018
Let [Formula: see text] be a graph and [Formula: see text] a non-negative integer. Suppose [Formula: see text] is a mapping from the vertex set of [Formula: see text] to [Formula: see text]. If, for any vertex [Formula: see text] of [Formula: see text], the number of neighbors [Formula: see text] of [Formula: see text] with [Formula: see text] is less than or equal to [Formula: see text], then [Formula: see text] is called a [Formula: see text]-relaxed [Formula: see text]-coloring of [Formula: see text]. And [Formula: see text] is said to be [Formula: see text]-colorable. The [Formula: see text]-relaxed chromatic number of [Formula: see text], denote by [Formula: see text], is defined as the minimum integer [Formula: see text] such that [Formula: see text] is [Formula: see text]-colorable. Let [Formula: see text] and [Formula: see text] be two positive integers with [Formula: see text]. Denote by [Formula: see text] the path on [Formula: see text] vertices and by [Formula: see text] the [Formula: see text]th power of [Formula: see text]. This paper determines the [Formula: see text]-relaxed chromatic number of [Formula: see text] the [Formula: see text]th power of [Formula: see text].