Name
Abstract | ||
|---|---|---|
Polar graphs generalise bipartite graphs, cobipartite graphs, and split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP-complete problem. Here, we show that for permutation graphs this problem can be solved in polynomial time. The result is surprising, as related problems like achromatic number and cochromatic number are NP-complete on permutation graphs. We give a polynomial-time algorithm for recognising graphs that are both permutation and polar. Prior to our result, polarity has been resolved only for chordal graphs and cographs. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ejc.2011.12.007 | Eur. J. Comb. |
Keywords | Field | DocType |
complete graph,polar permutation graph,bipartite graph,recognising graph,polynomial-time recognisable,cobipartite graph,polar graph,arbitrary graph,chordal graph,split graph,complete multipartite graph,permutation graph | Permutation graph,Discrete mathematics,Indifference graph,Combinatorics,Chordal graph,Multipartite graph,Cograph,Pathwidth,1-planar graph,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
34 | 3 | 0195-6698 |
Citations | PageRank | References |
3 | 0.42 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tınaz Ekim | 1 | 57 | 5.77 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Daniel Meister | 3 | 144 | 17.61 |