# Solving partition problems with colour-bipartitions

This paper was the culmination of my undergraduate research on monopolar graphs with Jing Huang. Having already shown how to find monopolar partitions of line graphs and claw-free graphs, we extended our technique to a class of graphs including those with no induced cycle of length 5 or greater. Our solution works for every graph class for which the monopolar partition problem is known to be polynomially-solvable, and also can be adapted to solve the related unipolar partition problem for general graphs.

This paper also proves an important relationship between the polar and monopolar partition problems: if a polar partition of a graph is already known, it can be decided in polynomial time whether the graph is monopolar.

This research was completed in the summer of 2010, my last undergraduate research term. I am grateful to NSERC for funding my work with a Undergraduate Student Research Award, and to my supervisor and coauthor Jing Huang.

Solving partition problems with colour-bipartitions.

*Graphs and Combinatorics*30(2). Ross Churchley and Jing Huang (2014). ↩︎