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)

zbMATH Keywords

algorithmsforbidden subgraphsDelaunay graphsGabriel graphsproximity graphscolouring problemsrelative neighbourhood graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• A Linear Algorithm for Colouring Planar Graphs with Five Colours
• A batching method for coloring planar graphs
• A linear 5-coloring algorithm of planar graphs
• 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
• 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 Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• The expected size of some graphs in computational geometry
• The relative neighbourhood graph of a finite planar set

Cited in

(3)

• Proximity graphs: {\(E, \delta\)}, {\(\Delta\)}, {\(\chi\)} and {\(\omega\)}
• Characterizing proximity trees
• 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)