应数学与统计学院张和平教授和徐守军教授邀请，南开大学计算机学院黄申为副教授将于2020年9月2日进行线上学术报告。

报 告：$k$-Critical Graphs in $P_5$-Free Graphs

时 间：9月2日下午4:50

地 点：腾讯会议， ID:877 660 728， 密码:0902

摘要：Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$.

Let $P_t$ be the path on $t$ vertices. 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 class 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 arguments and the dual of Dilworth's Theorem -- that may be of independent interest.

欢迎广大师生参加！

报告人简介

黄申为，博士毕业于加拿大西门飞沙大学，现为南开大学计算机学院副教授。主要从事图算法和图论的研究，截止目前在国际高水平期刊和会议上共发表论文20余篇。现主持国家自然科学基金青年项目一项。

甘肃省应用数学与复杂系统重点实验室

数学与统计学院

萃英学院

2020年8月31日