当前位置: 首页  科学研究  学术交流  学术报告

数学学科离散数学研究所学术报告(史永堂教授 南开大学,黄申为副教授 南开大学)

发布者:戴 情   发布时间:2021-12-23  浏览次数:186

报告一

报告题目:Some new results on Lagrangians of hypergraphs

报告人:史永堂教授 南开大学

报告时间:2021-12-24, 下午2:30-3:30

报告地点:腾讯会议,会议ID649-124-961

摘要:

 

 

报告二

报告题目:k-critical graphs in P5-free graphs

报告人:黄申为教授 南开大学

报告时间:2021-12-29, 上午10:30-11:30

报告地点:腾讯会议,会议ID517-381-998

摘要:A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. The study of $k$-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph classes is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this talk, we give a complete classification of the finiteness of $k$-vertex-critical graphs in the class of $(P_5,H)$-free graphs for all graphs $H$ on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs $H$ using various techniques such as Ramsey-type argument and Dual Dilworth's Theorem that may be of independent interest. 

 

邀请人:朱绪鼎