报告题目：An Optimal $\chi$-Bound for ($P_6$, diamond)-Free Graphs
报告人：南开大学黄申为副教授
报告时间：2022年3月17日9:30-12:30
腾讯会议ID：168260736
报告摘要：In this talk, we show that every ($P_6$, diamond)-free graph $G$ satisfies $\chi(G)\le \omega(G)+3$, where $\chi(G)$ and $\omega(G)$ are the chromatic number and clique number of $G$, respectively. Our bound is attained by the complement of the famous 27-vertex Schl\"afli graph.
Our result unifies previously known results on the existence of linear $\chi$-binding functions for several graph classes. Our proof is based on a reduction via the Strong Perfect Graph Theorem to imperfect ($P_6$, diamond)-free graphs, a careful analysis of the structure of those graphs, and a computer search that relies on a well-known characterization of 3-colourable $(P_6, K_3)$-free graphs.
报告人简介：黄申为博士，硕士毕业于上海大学数学系，师从上海市曙光学者康丽英教授，博士毕业于加拿大西蒙弗雷泽大学(Simon Fraser University)，师从美国工业与应用数学会会士(SIAM Fellow)Pavol Hell教授。博士毕业后分别在澳大利亚新南威尔士大学与加拿大劳里埃大学从事博士后工作，2018年入选南开大学百名青年学科带头人。
主要从事图论及其应用、理论计算机科学等方面的研究，博士论文获2016年度加拿大全国优秀博士论文，截止目前在国际期刊和会议上共发表论文30余篇。现为中国运筹学会图论组合分会青年理事以及天津市工业与应用数学学会理事。
