东南大学林文松教授; 兰州交通大学李敬文教授 学术报告

时间:2020-10-28浏览:13设置

图与组合系列前沿讲座:

报告题目:On t-relaxed 2-distant circular coloring of graphs

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

报告时间:2020年11月2日9:00-11:00

报告地点:腾讯会议ID: 947 685 718

摘要:  Let k be a positive integer. For any two integers i and j in {0, 1, . . . , k−1}, let |i−j|k be the circular distance between i and j, which is defined as min{|i − j|, k−|i − j|}. Suppose f is a mapping from V(G) to {0, 1, . . . , k−1}. If, for any two adjacent vertices u and v in V(G), |f(u)−f(v)|k ≥2, then f is called a k/2 -coloring of G. In this paper, we study the relaxation of k/2 -coloring. If adjacent vertices receive different integers, and for each vertex u of G, the number of neighbors v of u with |f(u)−f(v)|k=1 is at most t, then f is called a t-relaxed 2-distant circular k-coloring, or simply a (k/2 , t)-coloring of G. If G has a (k/2 , t)-coloring, then G is called (k/2 , t)-colorable. We prove that, for any two fixed integers k and t with k ≥ 2 and t ≥ 1, the problem of deciding whether a graph G is (k/2 , t) -colorable is NP-complete except the case k = 2 and the case k = 3 and t ≤ 3, which are polynomially solvable. For any outerplanar graph G, it is easy to see that G is (6/2 , 0)-colorable. We show that all outerplanar graphs are (5/2 , 4)-colorable and there is no fixed positive integer t such that all outerplanar graphs are (4/2 , t)-colorable. 

报告人简介:林文松,教授,博士生导师。2001至2004年就读于香港浸会大学数学系,获博士学位。长期从事运筹学方面的教学和科研工作。主要研究方向:图论及其应用、组合最优化。先后主持完成国家自然科学基金面上项目3项,主持江苏省自然科学基金面上项目1项。已在《J. Graph Theory》,《J. Combin. Theory Ser. B》, 《European J. Combin.》,《Discrete Appl. Math.》,《Discrete Math.》等国际权威学术期刊发表论文七十余篇。

 

邀请人:黄丹君

   

 

报告题目:随机图的邻点可区别边染色算法和优美标号算法

报  告  人:李敬文  兰州交通大学教授

报告时间:2020年11月2日9:00-11:00

报告地点:腾讯会议ID: 947 685 718

摘要:  对于简单连通图,当相邻边颜色和相邻顶点的由关联边构成的色集合均不同,且所用颜色数最小时,称其为图的邻点可区别边染色,也称图的邻强边染色,该染色概念是由兰交大张忠辅教授提出的,同时提出了相关猜想。目前国内外众多研究者得到了许多不错的结果,但大部分是针对特殊图的。针对随机图设计了一种新的启发式搜索算法,该算法根据邻点可区别边染色条件确立两个子目标函数和一个总目标函数,利用交换规则逐步寻优,直到目标函数值满足要求时结束。给出了详细的算法设计步骤及流程,也给出了测试和分析过程,测试结果表明该算法可以快速高效的求出满足猜想的邻点可区别边色数,算法时间复杂度不超过 O(f(n3))。

  设图G的顶点数为p,边数为q,如果存在一个单射f:V(G)→{0,1,2,…,q},使得边标号集合{f(uv)|uv∈E(G)}={1,2,…,q},且边标号满足f(uv)=|f(u)-f(v)|,则称G为优美图,f为G的一个优美标号。优美标号源于Rosa的“优美树猜想”,该猜想指出:所有的树都是优美的。许多特殊的图现已被证明是优美图,对于随机的、一般的图,目前并没有好的方法来证明图的优美性,该问题是NP困难的。针对上述问题,设计并提出了两种图的优美标号算法,分别是“基于优美空间搜索优美图算法”和“基于邻接矩阵判定优美图算法”,该算法可以解决有限点内任意图的优美性。 

报告人简介:李敬文,教授,研究方向为图论算法及其应用。先后主持完成三项国家自然科学基金资助项目(其中两个面上项目);分别获得省级科技进步奖2个一等奖,1个二等奖和3个三等奖;共发表学术论文100余篇,其中被SCI、EI或ISTP检索论文30余篇。

 

邀请人:黄丹君


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