List-monopolar partitions of claw-free graphs

The list monopolar partition problem asks whether a graph G together with lists L(v) ⊆ {0, 1}, v ∈ V(G) admits a mapping f: V(G) → {0, 1} such that f(v) ∈ L(v) for each source induces an independent set and f−1(1) induces a disjoint union of cliques in G. This problem is NP-complete in general. We show that the problem is solvable in time O(n2m) for claw-free graphs where n and m are the numbers of vertices and edges respectively in the input graph.

List-monopolar partitions of claw-free graphs. Ross Churchley and Jing Huang. Discrete Mathematics 312 (17), 2545–2549. September 2012.

Line-polar graphs: characterization and recognition

A graph is polar if its vertex set can be partitioned into A and B in such a way that A induces a complete multipartite graph and B induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite, cobipartite, and split graphs. The problem of recognizing polar graphs is NP-complete in general. However, it has been shown to be polynomial for several classes of graphs, including cographs and chordal graphs. In this paper, we study the problem of recognizing graphs whose line graphs are polar. It turns out that the core part of this problem lies in determining whether the edge set of a graph admits a partition (A, B) so that A induces a P3-free subgraph (i.e., a matching) and B induces a P4-free subgraph. We give a structural characterization of such graphs. The characterization enables us to devise an O(n) time algorithm to solve the stated recognition problem.

Line-polar graphs: characterization and recognition. Ross Churchley and Jing Huang. SIAM Journal on Discrete Mathematics 25 (3), 1269–1284. August 2011.