3-Graph Coloring

In this case, we wish to determine whether or not a graph is 3-colorable.

Parameters

Filters

Displaying 7 of 7 algorithms


Beigel & Eppstein	2000	$O(1.3289^n)$	$O(n^2)$
Beigel & Eppstein	1995	$O(1.3446^n)$	$O(n^2)$
Schiermeyer	1994	$O(1.415^n)$	$O(nm+n^2)$ loose bound, possibly $O(n+m)$
Petford and Welsh	1989	$O(n \log n)$	$O(n)$
Brélaz (DSatur)	1979	$O(n^2)$	$O(m+n)$
Lawler	1976	$O(mn 3^{n/3}) ~ O(mn(1.445)^n)$	$O(n)$
Brute-force search	1852	$O((m+n) 3^n)$	$O(n)$

Insuffient Data to display table

Displaying 3 of 3 other relevant algorithms