應(yīng)yl7703永利官網(wǎng)張和平教授和徐守軍教授邀請(qǐng)，南開大學(xué)計(jì)算機(jī)學(xué)院黃申為副教授將于2020年9月2日進(jìn)行線上學(xué)術(shù)報(bào)告。

報(bào) 告：$k$-Critical Graphs in $P_5$-Free Graphs

時(shí) 間：9月2日下午4:50

地 點(diǎn)：騰訊會(huì)議， 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.

歡迎廣大師生參加！

報(bào)告人簡(jiǎn)介

黃申為，博士畢業(yè)于加拿大西門飛沙大學(xué)，現(xiàn)為南開大學(xué)計(jì)算機(jī)學(xué)院副教授。主要從事圖算法和圖論的研究，截止目前在國(guó)際高水平期刊和會(huì)議上共發(fā)表論文20余篇?，F(xiàn)主持國(guó)家自然科學(xué)基金青年項(xiàng)目一項(xiàng)。

甘肅省應(yīng)用數(shù)學(xué)與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室

yl7703永利官網(wǎng)

萃英學(xué)院

2020年8月31日