A simple nc recognition algorithm for welsh-powell opposition graphs
D. Link, Stephan Olariu · International Journal of Computer Mathematics · 1991
The Welsh-Powell opposition graphs have been shown to be graphs for which a certain greedy heuristic results in an optimum colouring. We propose a new characterization for this class of graphs and exploit this result for the purpose of obtaining an efficient NC recognition algorithm.