报告人：林文松

工作单位：东南大学

报告时间：2018年11月10日18:00

报告地点：数学与统计学院一楼报告厅

报告摘要：

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 spt 2(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.

报告人简介：

林文松：东南大学数学学院教授、博士生导师。从事运筹学方面的教学和科研工作。主要研究方向：图论及其应用、组合最优化。先后主持国家自然科学基金面上项目3项，主持江苏省自然科学基金面上项目1项。已发表学术论文六十余篇。