Papers
In my undergraduate days at UVic, I spent two summer terms and a fair amount of the spring doing research on monopolar graphs under Dr Jing Huang. In summer 2009, we found a polynomial-time algorithm for recognizing monopolar line graphs; in 2010, we generalized the algorithm to claw-free graphs and then to a much larger graph class. This research, which was supported by two NSERC Undergraduate Student Research Awards and an Undergraduate Research Scholarship from UVic, led to the following four papers:
- R. Churchley and J. Huang, Line-polar graphs: characterization and recognition, SIAM J. Discrete Math 25 (2011) 1269–1284. doi:10.1137/100789208
- R. Churchley and J. Huang, List-monopolar partitions of claw-free graphs, Discrete Mathematics (2011), in press. doi:10.1016/j.disc.2011.08.022
- R. Churchley and J. Huang, The polarity and monopolarity of claw-free graphs, 2010. Submitted.
- R. Churchley and J. Huang, Solving partition problems with colour-bipartitions, 2011. Submitted.
Towards the end of my undergraduate degree, we started looking at generalizing our techniques to other partition problems. I became interested in the following (very general) problem: given induced-hereditary properties P1, P2, and Q, what is the complexity of determining whether the vertices of a graph in Q can be partitioned into two sets, one inducing a graph in P1 and the other inducing a graph in P2? Problems of this type are the subject of my current research.
- R. Churchley, J. Huang, and X. Zhu, Complexity of cycle transverse matching problems. To appear in Lecture Notes in Computer Science.
