Petford and Welsh (3-Graph Coloring Graph Coloring)

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O(n \log n)$

Space Complexity

$O(n)$ words

(Derived: we store the coloring of each vertex in a dictionary and the maximum size of this dictionary is equal to the number of vertices in the graph, n.)

Description

Approximate?

Exact

Randomized?

Yes, Monte Carlo

Model of Computation

Word RAM

Year

1989

Reference

https://www.sciencedirect.com/science/article/pii/0012365X89902148

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Petford_and_Welsh_(3-Graph_Coloring_Graph_Coloring)&oldid=47301"