Monopolar Graphs
Here is a collection of known results about the class of monopolar graphs. If I have missed something, or if you are interested in seeing the proof of an unpublished result, please let me know at rchurchl@uvic.ca.
Definition. A graph G is monopolar if its vertices can be partitioned into A and B such that A induces an independent set and B induces a disjoint union of cliques.
Interesting Inclusions
Special cases of monopolar partitions include bipartitions and split partitions; every bipartite graph and every split graph is therefore monopolar. Monopolar graphs are an important subclass of polar graphs.
Properties of Monopolar Graphs
- Every induced subgraph of a monopolar graph is also monopolar.
- The disjoint union of monopolar graphs is monopolar.
- A monopolar graph G with no isolated vertices has at most |E(G)| maximal cliques.
- If G is a monopolar graph with maximum clique size ω(G), then its chromatic number χ(G) is either ω(G) or ω(G)+1.
Characterizations
- Nine forbidden induced subgraphs (and their complements) characterize the cographs which are either monopolar or the complement of a monopolar graph. [Tınaz Ekim, N.V.R. Mahadev, and Dominique de Werra]
- There are infinitely many forbidden induced subgraphs for monopolar line graphs of bipartite graphs; their root graphs have been catalogued. [Jing Huang and Baogang Xu]
- There are also infinitely many minimal non-monopolar chordal graphs, which can be generated by a graph grammar. [Juraj Stacho]
- Monopolar claw-free graphs have a structural characterization using special vertex sequences. [Ross Churchley and Jing Huang]
Complexity results: recognition
- Recognizing monopolarity is an NP-complete problem. [Alastair Farrugia]
- Recognizing monopolarity in triangle-free graphs is NP-complete. [Ross Churchley and Jing Huang]
- Monopolar cographs can be recognized in polynomial time. [Tınaz Ekim, N.V.R. Mahadev, and Dominique de Werra]
- Monopolar chordal graphs can be recognized in linear time. [Tınaz Ekim, Pavol Hell, Juraj Stacho, and Dominique de Werra]
- Monopolar line graphs can be recognized in O(n) time. [Ross Churchley and Jing Huang] [Bipartite case by Tınaz Ekim and Jing Huang]
- Monopolar claw-free graphs can be recognized in O(n3) time. [Ross Churchley and Jing Huang] [Earlier O(n^4m^2) algorithm by Tınaz Ekim]
- Monopolar permutation graphs can be recognized in O(n+m^3) time. [Tınaz Ekim, Pinar Heggernes, and Daniel Meister]
- It can be determined in O(n^4) time whether a graph containing no cycle of length ≥ 5 is monopolar. [Ross Churchley and Jing Huang]
Complexity results: other
- The clique number ω(G) of a monopolar graph can be found in polynomial time.
- The colouring problem for monopolar graphs is NP-complete.
- Recognizing monopolarity in comparability graphs is NP-complete.
