Coloring certain proximity graphs (Q917569)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4156467
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Coloring certain proximity graphs |
scientific article; zbMATH DE number 4156467 |
Statements
Coloring certain proximity graphs (English)
0 references
1990
0 references
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.
0 references
colouring problems
0 references
proximity graphs
0 references
Delaunay graphs
0 references
relative neighbourhood graphs
0 references
Gabriel graphs
0 references
forbidden subgraphs
0 references
algorithms
0 references
0.7864914536476135
0 references
0.7598063945770264
0 references
0.7574251890182495
0 references
0.7574251890182495
0 references
