A batching method for coloring planar graphs

DOI10.1016/0020-0190(78)90065-0MaRDI QIDQ1252864zbMATH OpenOpenAlexFDO

Authors Richard J. Lipton, Raymond E. Miller

Publication date 1978

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(78)90065-0

zbMATH Keywords

Batching MethodColouring Planar GraphsFinite GraphVertex Colouring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cited in

(9)

• On linear-time algorithms for five-coloring planar graphs
• A fast parallel coloring of planar graphs with five colors
• A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
• Parallel construction of subdivision hierarchies
• Batch sizes for the batching method of colouring planar maps
• Planar graphs with few vertices of small degree
• Branch-and-bound techniques for the maximum planar subgraph problem^∗
• Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
• Coloring certain proximity graphs

This page was built for publication: A batching method for coloring planar graphs

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