4-Graph Coloring: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 36: | Line 36: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Graph Coloring - 4-Graph Coloring - Time.png|1000px]] | [[File:Graph Coloring - 4-Graph Coloring - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Graph Coloring - 4-Graph Coloring - Space.png|1000px]] | [[File:Graph Coloring - 4-Graph Coloring - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:Graph Coloring - 4-Graph Coloring - Pareto Frontier.png|1000px]] | [[File:Graph Coloring - 4-Graph Coloring - Pareto Frontier.png|1000px]] | ||
Revision as of 13:05, 15 February 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 | |
| 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
Pareto Frontier Improvements Graph
References/Citation
https://link.springer.com/chapter/10.1007/978-3-540-73545-8_9