报告题目1：Characterization of chordal circular-arc graphs
报告人：操宜新，香港理工大学
报告时间：2024年6月4日（周二）15:00-17:00
报告地点：20-200
报告摘要：The most elusive problem around the class of circular-arc graphs is identifying all forbidden induced subgraphs, i.e., minimal graphs that are not in this class. The main obstacle is the lack of a systematic way of enumerating them. McConnell [FOCS 2001] presented a transformation from circular-arc graphs to interval graphs with certain patterns of representations. We fully characterize these interval patterns for chordal circular-arc graphs, thereby building a connection between minimal chordal forbidden induced subgraphs of circular-arc graphs and those of interval graphs. We use this connection to derive all minimal chordal graphs that are not circular-arc graphs.
报告人简介：操宜新博士是香港理工大学计算学系的副教授，2012年博士毕业于德州农机大学。在2014年回国之前，他在匈牙利科学院做了两年的研究员。他的研究兴趣包括算法图论，细粒度复杂性和算法设计，组合优化，以及它们在生物信息学和社交网络中的应用。他的研究得到了香港研究资助委员会（RGC）和国家自然科学基金（NSFC）的支持。目前主要学术兼职包括中国计算机学会理论计算机科学专业委员会常务委员和中国运筹学会数学规划分会理事和图论组合分会理事。
报告题目2：Min-order and dichotomy
报告人：黄靖，University of Victoria（加拿大维多利亚大学）
报告摘要：Min-order of digraphs is a vertex ordering property that unifies several seemingly different graph and digraph classes under one umbrella. These classes are all broadly speaking different generalizations of interval graphs, and include, in addition to interval graphs, also adjusted interval digraphs, threshold graphs, complements of threshold tolerance graphs (known as `co-TT' graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray graphs.Suprisingly, the min-order provides a bounday between the easy and hard cases for a certain type of graph homomorphism problems. In this talk I will illustrate some structural properties as well as a geometric representation of min-orderable graphs and digraphs. These are in a sense the key to the proofs of dichotomy
theorems for the graph homomorphism problems.
报告人简介：加拿大维多利亚大学教授，博士生导师，于1986、1992年在中央研究院、西蒙菲莎大学分别获得硕士和博士学位。1992年至1997年分别在南丹麦大学、英属哥伦比亚数学与统计部、科廷大学获得博士后职位从事博士后研究。黄靖教授在图论，算法和复杂性、算法图论等领域研究中取得了重要成果，并多次应邀做大会报告和邀请报告。目前已正式发表学术论七十余篇，发表在Combinatorics, JCTB, SIDMA，JGT, EJC等国际重要期刊。
邀请人：朱绪鼎