5-Graph Coloring: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "{{DISPLAYTITLE:5-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 5-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 2-Graph Coloring, 3-Graph Coloring, 4-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb...")
 
No edit summary
 
(One intermediate revision by the same user not shown)
Line 12: Line 12:
== Parameters ==  
== Parameters ==  


<pre>n: number of vertices
$n$: number of vertices
m: number of edges</pre>
 
$m$: number of edges


== Table of Algorithms ==  
== Table of Algorithms ==  


{| class="wikitable sortable"  style="text-align:center;" width="100%"
Currently no algorithms in our database for the given problem.
 
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference
 
|-
 
| [[Karger, Blum ( Graph Coloring)|Karger, Blum]] || 1997 || $O(poly(V))$ ||  || $\tilde{O}(n^{3/14})$ || Deterministic || [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.4204 Time]
|-
|}


== References/Citation ==  
== References/Citation ==  


https://drops.dagstuhl.de/opus/volltexte/2021/14182/pdf/LIPIcs-ICALP-2021-113.pdf
https://drops.dagstuhl.de/opus/volltexte/2021/14182/pdf/LIPIcs-ICALP-2021-113.pdf

Latest revision as of 08:53, 10 April 2023

Description

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

Related Problems

Generalizations: k-Graph Coloring

Related: Chromatic Number, 2-Graph Coloring, 3-Graph Coloring, 4-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

Currently no algorithms in our database for the given problem.

References/Citation

https://drops.dagstuhl.de/opus/volltexte/2021/14182/pdf/LIPIcs-ICALP-2021-113.pdf