4-Graph Coloring

Description

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

Related Problems

Generalizations: k-Graph Coloring

Related: Chromatic Number, 2-Graph Coloring, 3-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring

Parameters

n: number of vertices

m: number of edges

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Brute force	1852	$O((m+n)*{4}^n)$	$O(n)$ auxiliary	Exact	Deterministic
Karger, Blum	1997	$O(poly(V))$		$\tilde{O}(n^{3/14})$	Deterministic	Time
Fomin; Gaspers & Saurabh	2007	$O({1.7272}^n)$	$O(n)$	Exact	Deterministic	Time
Lawler	1976	$O((m + n)*{2}^n)$	$O(n+m)$	Exact	Deterministic	Time
Byskov	2004	$O({1.7504}^n)$	$O(n^{2})$?	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff

References/Citation

https://link.springer.com/chapter/10.1007/978-3-540-73545-8_9