Non-realizability of as a semi-arc -visibility graph
Non-realizability of as a semi-arc -visibility graph
Let denote the complete graph on vertices, and let a semi-arc -visibility graph be a graph represented by semi-arcs with visibility determined by at most blockers. Complete-graph non-realizability conjecture. The complete graph is not a semi-arc -visibility graph.
This conjecture is presented as a consequence of the preceding maximum-edge conjecture: applying that bound at would give fewer than the edges of the complete graph. It remains open in the supplied source.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Matthew Babbitt, J. T. Geneson and Tanya Khovanova, “On k-visibility graphs”, arXiv:1305.0505 (2014).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.