Coloring certain proximity graphs (Q917569)

There is shown that colouring problems are somewhat easier when we consider three classes of proximity graphs: Delaunay graphs, relative neighbourhood graphs and Gabriel graphs. These graphs are more restrictive with regard to the containment of forbidden subgraphs and they are sparser than general planar graphs on the average. Given algorithms (with lower time of complexity) are better to other known methods.