Coloring certain proximity graphs

DOI10.1016/0898-1221(90)90032-FzbMath0705.05032MaRDI QIDQ917569

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)

Related Items (1)

Coloring certain proximity graphs

Cites Work

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

This page was built for publication: Coloring certain proximity graphs