Small-independent-set conjecture for triangle-free intersection graphs of boxes
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.
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
Sign in to submit a solution.
No solutions have been posted yet.