The monopolar partition problem in restricted graph classes

Talks given at CanaDAM 2011, CMS Winter Meeting, and discrete math seminars

A graph is called monopolar if its vertices can be partitioned into an independent set and a disjoint union of cliques. My undergraduate research with Jing Huang studied monopolar partitions in line graphs, claw-free graphs, and other graph classes.

I presented our results at various conferences and seminars, and you can find the slides of each below:

Monopolar partitions: easy to learn, NP-hard to master
UVic discrete math seminar (September 27, 2010)
Monopolar claw-free graphs: characterization and recognition
UVic discrete math seminar (October 25, 2010)
Monopolar claw-free graphs
Canadian Mathematics Society Winter Meeting (December 4, 2010)
Partitioning graphs via edge-coloured homomorphisms
Canadian Discrete and Algorithmic Mathematics Conference (June 1, 2011)
A survey on monopolar graphs: algorithms and complexity
SFU computer science seminar (June 13, 2013)