The minimum-edge non-TRVG conjecture for K3,5K_{3,5}

Let a transparent rectangle visibility graph (TRVG) be a graph admitting a representation by axis-parallel rectangles in which two vertices are adjacent when their rectangles are visible to one another, and call a graph that has no such representation a non-TRVG. The complete bipartite graph K3,5K_{3,5} has 1515 edges.

Minimum-edge non-TRVG conjecture. K3,5K_{3,5} is a non-TRVG with the least number of edges.

The paper establishes that K3,5K_{3,5} is a non-TRVG and reports that no non-TRVG with fewer than 1515 edges was found; the conjectured minimality remains open.

Sources & referencesView supporting material

Primary source

Chaipattana Juntarapomdach and Teeradej Kittipassorn, “Transparent Rectangle Visibility Graphs”, arXiv:2506.14522 (2025).

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.