Ross Churchley (SFU)

A survey on monopolar graphs: algorithms and complexity
Ross Churchley (Simon Fraser University, Math.)


A graph is called “monopolar” if its vertices can be partitioned into an independent set and a disjoint union of cliques. It is generally NP-complete to decide whether an given input graph is monopolar. A flurry of papers in the last five years has identified several graph classes (e.g. chordal graphs, line graphs, permutation graphs) where monopolarity can be decided in polynomial time, and others (e.g. planar graphs, triangle-free graphs) where the problem remains NP-complete. This talk will survey these results, show how they can all be derived from observations about a few small structures, and propose new questions for future research.


Friday, December 6, 2013


12:30 pm - 1:30 pm

TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby