4-Graph Coloring

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

Parameters

$n$ : number of vertices
$m$ : number of edges

Related Problems

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms

				See more
Fomin; Gaspers & Saurabh	2007	$O(1.7272^n)$	$O(n)$
Byskov	2004	$O(1.7504^n)$	$O(n^2)$
Lawler	1976	$O((m+n)2^n)$	$O(n)$
Brute force	1852	$O((m+n) 4^n)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table