On the polarity and monopolarity of graphs

Paper with Jing Huang published in the Journal of Graph Theory

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 shows that everything you need to know about monopolar partitions in claw-free graphs can be uncovered by listing some rules for pairs of vertices in the graph and following the direct implications.

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.

Ross Churchley and Jing Huang [1]

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

  1. On the polarity and monopolarity of graphs. Journal of Graph Theory 76(2). Ross Churchley and Jing Huang (2014). ↩︎