Closure of co-bipartite unit disk graphs under bipartite complementation

Let GG be a co-bipartite unit disk graph, meaning that its vertex set can be partitioned into two cliques, and let the bipartite complement of GG 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 C4C_4-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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.