Coloring certain proximity graphs

DOI10.1016/0898-1221(90)90032-FMaRDI QIDQ917569zbMATH OpenFDO

Authors Robert J. Cimikowski

Publication date 1990

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(90)90032-F

zbMATH Keywords

algorithmscolouring problemsDelaunay graphsforbidden subgraphsGabriel graphsproximity graphsrelative neighbourhood graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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.

Recommendations

• Proximity graphs: {\(E, \delta\)}, {\(\Delta\)}, {\(\chi\)} and {\(\omega\)}
• scientific article; zbMATH DE number 1843872
• Some properties of k-Delaunay and k-Gabriel graphs
• Characterizing proximity trees
• On structural and graph theoretic properties of higher order Delaunay graphs

Cites work

• A batching method for coloring planar graphs
• A linear 5-coloring algorithm of planar graphs
• A Linear Algorithm for Colouring Planar Graphs with Five Colours
• Almost all k-colorable graphs are easy to color
• An upper bound on the shortness exponent of inscribable polytopes
• Coloring certain proximity graphs
• Every planar map is four colorable. I: Discharging
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• New methods to color the vertices of a graph
• On linear-time algorithms for five-coloring planar graphs
• On uniquely colorable planar graphs
• Parallel concepts in graph theory
• Some simplified NP-complete graph problems
• The Complexity of Near-Optimal Graph Coloring
• The expected size of some graphs in computational geometry
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• The relative neighbourhood graph of a finite planar set

Cited in

(3)

• Characterizing proximity trees
• Proximity graphs: {\(E, \delta\)}, {\(\Delta\)}, {\(\chi\)} and {\(\omega\)}
• Coloring certain proximity graphs

This page was built for publication: Coloring certain proximity graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q917569)