题 目： Some partition problems on graphs

报告人：Professor Jing Huang (黄靖教授)
Department of Mathematics and Statistics
University of Victoria，Canada

时 间：2011年3月22日 上午10:00-10:50

地 点：华东师大闵行校区数学系102报告厅

摘要：Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions, which are hard to recognize in general. It has been shown however that, among several classes of graphs such as cographs, chordal graphs, and line graphs, both properties are recognizable in polynomial time. In this talk we address the two recognition problems for claw-free graphs, arguing that the recognition of the polarity is in essence of the satisfiability problem and hence an NP-complete problem and the recognition of monopolarity is solvable in polynomial time. Thus claw-free graphs demonstrate a contrast between the two problems. The polynomial time algorithm for recognizing monopolar claw-free graphs resembles the well-known breadth first search algorithm and is based on a structural characterization of the graphs. This work is joint with Ross Churchley.