Document Zbl 0653.68069

A fast parallel coloring of planar graphs with five colors. (English) Zbl 0653.68069

Inf. Process. Lett. 25, 51-53 (1987).

MSC:

68R10	Graph theory (including graph drawing) in computer science
68Q25	Analysis of algorithms and problem complexity
05C15	Coloring of graphs and hypergraphs

Keywords:

coloring of planar graphs; parallel algorithms

Cite Review PDF

Full Text: DOI

References:

[1]	Appel, K.; Haken, W., Every planar map is four-colorable, Illinois J. Math., 21, 429-567 (1977) · Zbl 0387.05009
[2]	Bauernöppel, F.; Jung, H., Fast parallel vertex coloring, (Fundamentals of Computation Theory. Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 199 (1985), Springer: Springer Berlin), 28-35 · Zbl 0584.05038
[3]	J. Boyar and H. Karloff, Coloring planar graphs in parallel, J. Algorithms, Submitted for publication.; J. Boyar and H. Karloff, Coloring planar graphs in parallel, J. Algorithms, Submitted for publication. · Zbl 0636.68088
[4]	Chiba, N.; Nishizeki, T.; Saito, N., A linear algorithm for five-coloring a planar graph, (Graph Theory and Algorithms. Graph Theory and Algorithms, Lecture Notes in Computer Science, Vol. 108 (1981), Springer: Springer Berlin), 9-19 · Zbl 0465.68034
[5]	Diks, K., A fast parallel algorithm for six-colouring of planar graphs, (12th Internat. Symp. on the Mathematical Foundations of Computer Science. 12th Internat. Symp. on the Mathematical Foundations of Computer Science, Bratislava (1986)) · Zbl 0601.05022
[6]	Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
[7]	Lipton, R. J.; Miller, R. E., A batching method for coloring planar graphs, Inform. Process. Lett., 7, 4, 185-188 (1978) · Zbl 0395.05032
[8]	Luby, M., A simple parallel algorithm for the maximal independent set, SICOMP, 15, 4 (1986) · Zbl 0619.68058

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.