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

From papers

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)(2n3k+62)(k+1)\left(2n-\frac{3k+6}{2}\right)

for n3k+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.

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

No solutions have been posted yet.