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.
Our results led to several papers:
I presented our results at various conferences and seminars. Here are my slides for a few of them:
This paper is the result of the research term I took as an undergraduate in the summer of 2009. It studies the edge versions of the monopolar and polar partition problems, and presents a linear-time solution to both.
Shortly after solving the monopolar partition problem for line graphs, Jing and I realized that our solution could be used to solve the "precoloured" version of the problem, and then further extended to claw-free graphs.
This is my favourite paper to come out of my research with Jing Huang at the University of Victoria, and the last one to be published. The main result is that the structure of monopolar partitions in claw-free graphs can be fully understood by looking at small subgraphs and following their direct implications on vertex pairs.
This paper was the culmination of my undergraduate research on monopolar graphs with Jing Huang. It shows that a single strategy can be used to solve the monopolar partition problem in all graph classes for which the problem was previously known to be tractable.