The semi-arc k-visibility graph edge-maximization conjecture

About 13 years old · traced to

A semi-arc kk-visibility graph is a graph represented by semi-arcs, with visibility allowing at most kk obstructing semi-arcs; let nn be the number of vertices. Semi-arc kk-visibility graph edge-maximization conjecture. The maximum number of edges in a semi-arc kk-visibility graph on nn vertices is

(k+1)(2n−3k+62)(k+1)\left(2n-\frac{3k+6}{2}\right)

for n≥3k+3n \geq 3k+3. 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.