4-Graph Coloring (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
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