东南大学林文松 教授学术报告

时间:2018-05-15浏览:13设置

报告人:林文松 教授(东南大学)


时    间:2018519日下午9:30 - 10:30  


地    点:数理信息学院21427


题    目: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.



浙江师范大学离散数学研究中心版权所有 © 2018-2028
地址:浙江省金华市迎宾大道688号21幢 邮政编码:321004
联系电话:0579-82282629   电子邮箱:jcsx@zjnu.cn    管理登陆