Small-independent-set conjecture for triangle-free intersection graphs of boxes
For , an intersection graph of boxes in has one vertex for each box and edges joining intersecting boxes; it is triangle-free when it has no -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 there exist and a triangle-free intersection graph of boxes in with independence number at most . Such a result would produce triangle-free box intersection graphs with independence number and address the open question highlighted in the source for boxes in dimension three or higher.
References
- István Tomon, “Coloring lines and Delaunay graphs with respect to boxes”, arXiv:2301.10129 (2023).
Progress summary
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.