4-Graph Coloring: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
n: number of vertices | $n$: number of vertices | ||
m: number of edges | $m$: number of edges | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 25: | Line 25: | ||
| [[Brute force (4-Graph Coloring Graph Coloring)|Brute force]] || 1852 || $O((m+n)*{4}^n)$ || $O(n)$ auxiliary || Exact || Deterministic || | | [[Brute force (4-Graph Coloring Graph Coloring)|Brute force]] || 1852 || $O((m+n)*{4}^n)$ || $O(n)$ auxiliary || Exact || Deterministic || | ||
|- | |- | ||
| [[Fomin; Gaspers & Saurabh (4-Graph Coloring Graph Coloring)|Fomin; Gaspers & Saurabh]] || 2007 || $O({1.7272}^n)$ || $O(n)$ || Exact || Deterministic || [https://link-springer-com.ezproxy.canberra.edu.au/chapter/10.1007/978-3-540-73545-8_9 Time] | | [[Fomin; Gaspers & Saurabh (4-Graph Coloring Graph Coloring)|Fomin; Gaspers & Saurabh]] || 2007 || $O({1.7272}^n)$ || $O(n)$ || Exact || Deterministic || [https://link-springer-com.ezproxy.canberra.edu.au/chapter/10.1007/978-3-540-73545-8_9 Time] | ||
Revision as of 08:53, 10 April 2023
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.ezproxy.canberra.edu.au/chapter/10.1007/978-3-540-73545-8_9