Closure of co-bipartite unit disk graphs under bipartite complementation
Closure of co-bipartite unit disk graphs under bipartite complementation
Let be a co-bipartite unit disk graph, meaning that its vertex set can be partitioned into two cliques, and let the bipartite complement of be the graph obtained by complementing the edges between the two parts while leaving the two cliques unchanged. Closure conjecture. For every co-bipartite unit disk graph, its bipartite complement is also a co-bipartite unit disk graph. The conjecture is motivated by the fact that the bipartite complement preserves the unit disk graph property for the subclass whose cross-part edges are -free, while the general closure question remains open.
Sources & referencesView supporting material
Primary source
Aistis Atminas and Viktor Zamaraev, “On forbidden induced subgraphs for unit disk graphs”, arXiv:1602.08148 (2016).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.