报告题目：Birkhoff-von Neumann Graphs that are PM-compact
报 告 人：王秀梅
工作单位：郑州大学数学与统计学院
报告时间：2021-11-25 15:00-17:00
腾讯会议ID：4170675239
报告摘要：
In any investigation concerning the perfect matching polytope, one may assume that $G$ is matching covered , that is, it is a connected graph (of order at least two) and each edge lies in some perfect matching. A graph $G$ is Birkhoff-von Neumann (BvN) if its perfect matching polytope is characterized solely by non-negativity and degree constraints. A result of Balas (1981) implies that $G$ is BvN if and only if $G$ does not contain a pair of vertex-disjoint odd cycles $(C_1,C_2)$ such that $G-V(C_1)-V(C_2)$ has a perfect matching. It follows immediately that the corresponding decision problem is in co-NP. However, it is not known to be in NP. The problem is in P if the input graph is planar --- due to a result of Carvalho, Lucchesi and Murty (2004). These authors, along with Kothari (2018), have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is $\overline{C_6}$-free.
报告人简介：
王秀梅，郑州大学教授，中国运筹学会理事，中国运筹学会图论组合分会理事，中国运筹学会数学优化分会理事，河南省运筹学会常务理事。主要从事图论与组合最优化的研究工作，共发表本研究方向专业学术论文20余篇，其中在数学类top期刊《Mathematical Programming A》发表论文1篇。曾主持2项国家自然科学基金、1项中国博士后科学基金面上资助项目、1项河南省基础与前沿技术研究计划项目, 曾参加的基金项目有7项。获河南省自然科学优秀论文一等奖2项，二等奖3项。获河南省教育厅优秀科技论文一等奖4项。
