Edge-coloring complete geometric graphs without monochromatic crossings
Let $S$ be a set of $n$ points in the plane in general position, and join every two points of $S$ by a straight segment. The edges are to be colored so that any two crossing edges receive different colors; by general position, all crossings are proper.
Each color class is then a plane geometric graph. Since $n$ points can be placed so that $n/2$ of the edges cross pairwise, $n/2$ colors are needed in general. Bose, Hurtado, Rivera-Campo and Wood showed that $n - \sqrt{n/12}$ colors always suffice.
Problem. What is the least number of colors that suffices for every set of $n$ points in general position?
Source: Hurtado; see Araujo, Dumitrescu, Hurtado, Noy and Urrutia (2005); Problem 75 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- complete geometric graph, crossing edges, edge coloring, The Open Problems Project
References
@article{araujo2005,
author = {Araujo, G. and Dumitrescu, Adrian and Hurtado, Ferran and Noy, M. and Urrutia, J.},
title = {On the chromatic number of some geometric type {Kneser} graphs},
journal = {Comput. Geom.},
volume = {32},
number = {1},
year = {2005},
pages = {59--69},
}
@article{bose2006,
author = {Bose, Prosenjit and Hurtado, Ferran and Rivera-Campo, Eduardo and Wood, David R.},
title = {Partitions of complete geometric graphs into plane trees},
journal = {Comput. Geom.},
volume = {34},
number = {2},
year = {2006},
pages = {116--125},
doi = {10.1016/j.comgeo.2005.08.006},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01107, "Edge-coloring complete geometric graphs without monochromatic crossings", clopen.solutions.