The superlinear crossing-family conjecture for geometric complete graphs

At least 16 years old · documented by

Let t(n)t(n) be the minimum number of colours needed to colour the edges of some geometric drawing of KnK_n so that every pair of edges with the same colour crosses; each colour class is a crossing family. Crossing-family conjecture. The colouring number satisfies

t(n)n→∞as n→∞.\frac{t(n)}{n}\rightarrow\infty\quad\text{as }n\rightarrow\infty.

Since each crossing family can be associated with blockers, this is stated as a strengthening of the superlinear blocking conjecture and remains open.

References

Primary source

Attila Pór and David R. Wood, “On Visibility and Blockers”, arXiv:0912.1150 (2009).

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.