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
Primary source
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.