Small-independent-set conjecture for triangle-free intersection graphs of boxes

From papers

For α>0\alpha>0, an intersection graph of nn boxes in R3\mathbb{R}^3 has one vertex for each box and edges joining intersecting boxes; it is triangle-free when it has no 33-cycle, and its independence number is the maximum size of a set of pairwise nonadjacent vertices. Small-independent-set conjecture for box graphs. For every α>0\alpha>0 there exist nn and a triangle-free intersection graph of nn boxes in R3\mathbb{R}^3 with independence number at most αn\alpha n. Such a result would produce triangle-free box intersection graphs with independence number o(n)o(n) and address the open question highlighted in the source for boxes in dimension three or higher.

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

István Tomon, “Coloring lines and Delaunay graphs with respect to boxes”, arXiv:2301.10129 (2023).

Solutions 0

No solutions have been posted yet.