报告主题：不含P5的k-临界图 （k-critical graphs in P5-free graphs）
报 告 人：黄申为 教授（南开大学）
报告时间：2021年11月15日（周一） 19:30
参会方式：腾讯会议
会议ID：937 166 301
邀请人：康丽英
报告摘要：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.