The semi-arc k-visibility graph edge-maximization conjecture
A semi-arc -visibility graph is a graph represented by semi-arcs, with visibility allowing at most obstructing semi-arcs; let be the number of vertices. Semi-arc -visibility graph edge-maximization conjecture. The maximum number of edges in a semi-arc -visibility graph on vertices is
for . This conjecture would determine the extremal edge count beyond the open range identified in the paper; the stated bound is conjectured to be tight.
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.