On the polarity and monopolarity of 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.

On the polarity and monopolarity of graphs. Journal of Graph Theory 76(2). Ross Churchley and Jing Huang (2014). Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions; graphs with polarity and monopolarity are respectively called polar and monopolar graphs. These two properties commonly generalize bipartite and split graphs, but are hard to recognize in general. In this article we identify two classes of graphs, triangle-free graphs and claw-free graphs, restricting to which provide novel impact on the complexity of the recognition problems. More precisely, we prove that recognizing polarity or monopolarity remains NP-complete for triangle-free graphs. We also show that for claw-free graphs the former is NP-complete and the latter is polynomial time solvable. This is in sharp contrast to a recent result that both polarity and monopolarity can be recognized in linear time for line graphs. Our proofs for the NP-completeness are simple reductions. The polynomial time algorithm for recognizing the monopolarity of claw-free graphs uses a subroutine similar to the well-known breadth-first search algorithm and is based on a new structural characterization of monopolar claw-free graphs, a generalization of one for monopolar line graphs obtained earlier.

We later generalized the proof to a technique we called "colour-bipartitions", but I look back on the original moment of inspiration most fondly.