时 间：2018年5月19日下午9:30 - 10:30

地 点：数理信息学院21幢427

题 目：On t-relaxed 2-distant coloring of a graph

摘 要：Let G be a simple graph. Suppose f is a mapping from V (G) to nonnegative integers. If, for any two adjacent vertices u and v of G, |f(u) − f(v)| ≥ 2, then f is called a 2-distant coloring of G. In this paper, we introduce a relaxation of 2-distant coloring of a graph. Let t be a nonnegative integer. Suppose f is a mapping from V (G) to nonnegative integers. If adjacent vertices receive different integers and for each vertex u of G, the number of neighbors v of u with |f(v) − f(u)| = 1 is at most t, then f is called a t-relaxed 2-distant coloring of G. If t = 0 then f is just a 2-distant coloring of G. The span of f, denote by sp(f), is the difference between the maximum and minimum integers used by f. The minimum span of a t-relaxed 2-distant coloring of G, is called t-relaxed 2-distant coloring span of G, denoted by spt2(G). This paper investigates the complexity of the t-relaxed 2-distant coloring problem as well as some properties of this parameter on planar and outerplanar graphs.