Non-realizability of K3k+4K_{3k+4} as a semi-arc kk-visibility graph

At least 12 years old · documented by

Let K3k+4K_{3k+4} denote the complete graph on 3k+43k+4 vertices, and let a semi-arc kk-visibility graph be a graph represented by semi-arcs with visibility determined by at most kk blockers. Complete-graph non-realizability conjecture. The complete graph K3k+4K_{3k+4} is not a semi-arc kk-visibility graph.

This conjecture is presented as a consequence of the preceding maximum-edge conjecture: applying that bound at n=3k+4n=3k+4 would give fewer than the (3k+42)\binom{3k+4}{2} edges of the complete graph. It remains open in the supplied source.

References

Primary source

Matthew Babbitt, J. T. Geneson and Tanya Khovanova, “On k-visibility graphs”, arXiv:1305.0505 (2014).

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.