学术题目：Graph and digraph classes arising from list homomorphism problems
报 告 人：加拿大维多利亚大学黄靖教授
邀 请 人：张霞
报告摘要：Fix a graph H, the list homomorphism problem for H asks whether a graph G together with lists L(v) ⊆ V (H), v ∈ V (G) admits a homomorphism f : G → H such that f(v) ∈ L(v), v ∈ V (G). List homomorphism problems for digraphs are defined analogously. The dichotomy of list homomorphism problems for graphs is well-understood.In particular, we understand exactly the graphs for which list homomorphism problems are polynomial time solvable. These include several well-studied classes of graphs such as interval graphs, the complements of 2-clique circular arc graphs, and bi-arc graphs. However,the digraph classes which define the dichotomy of list homomorphism problems for digraphs are not completely comprehended. We exhibit several classes of digraphs which share some common forbidden structures and for which the list homomorphism problems are polynomial time solvable. Surprisingly, one of the forbidden structures gives rise to beautiful bipartite analogues of the classical comparability and cocomparability graphs. This talk is based on joint work with Hell,Feder, Lin, McConnell, and Rafiey.
报告人简介：黄靖，加拿大维多利亚大学教授，博士生导师，于1986、1992年在中央研究院、西蒙菲莎大学分别获得硕士和博士学位。1992年至1997年分别在南丹麦大学、英属哥伦比亚数学与统计部、科廷大学获得博士后职位从事博士后研究。黄靖教授的研究领域为图论、算法与复杂性，在图结构、图算法方面获得多个重要的研究结果，迄今在J. Combinatorial Theory B, J. Graph Theory, SIAM Discrete Math., Discrete Appl. Math.等国际权威学术期刊发表论文70余篇。
报告时间：2019年7月4日(周四)上午10:00-11:00
报告地点：长清校区A231报告厅
欢迎各位老师和同学参加！
