My talk at the Canadian Mathematics Society’s 2010 Winter Meeting was my first-ever conference presentation. The talk was scheduled at 4:30 in a hotel suite halfway up the building, so we were treated to a beautifully distracting sunset. I appreciate everyone who looked at my slides instead of out the window.
The subject of my talk was a structural characterization of claw-free monopolar graphs and the polynomial-time recognition algorithm it implies. It was based on the research I did in my last year of undergrad and was submitted as “The polarity and monopolarity of claw-free graphs.”
ROSS CHURCHLEY, University of Victoria
Monopolar claw-free graphsA graph is called monopolar if its vertices can be partitioned into an independent set and a disjoint union of cliques. Monopolar graphs, which include all bipartite and split graphs, form an important subclass of the so-called polar graphs. We present a structural characterization of monopolar claw-free graphs which suggests a simple O(n^3) algorithm for their recognition. This contrasts with the NP-completeness of related recognition problems, including those for monopolar graphs in general and for polar claw-free graphs.
