3 - Graph Coloring: Difference between revisions
Jump to navigation
Jump to search
(Created page with "query") |
No edit summary |
||
| Line 1: | Line 1: | ||
== Problem Description== | |||
Graph coloring problem is to assign colors to certain elements of a graph subject to certain constraints. | |||
Vertex coloring is the most common graph coloring problem. The problem is, given m colors, find a way of coloring the vertices of a graph such that no two adjacent vertices are colored using same color. The other graph coloring problems like Edge Coloring (No vertex is incident to two edges of same color) and Face Coloring (Geographical Map Coloring) can be transformed into vertex coloring. | |||
== Bounds Chart == | |||
[[File:3_-_Graph_ColoringBoundsChart.png|1050px]] | |||
== Step Chart == | |||
[[File:3_-_Graph_ColoringStepChart.png|1050px]] | |||
== Improvement Table == | |||
{| class="wikitable" style="text-align:center;" width="100%" | |||
!width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links | |||
|- | |||
| rowspan="1" | Exp/Factorial | |||
| [- Brute-force search (1852)] | |||
[https://www.sciencedirect.com/science/article/pii/002001907690065X?via%3Dihub Lawler; 1976 (1976)] | |||
[https://link.springer.com/chapter/10.1007/3-540-57899-4_51 Schiermeyer; 1994 (1994)] | |||
[https://www.academia.edu/24381316/3-Coloring_in_time_O_1.3446_n_a_no-MIS_algorithm Beigel & Eppstein; 1995 (1995)] | |||
[https://www.sciencedirect.com/science/article/pii/S0196677404001117?via%3Dihub Beigel & Eppstein; 2005 (2000)] | |||
[https://www.cs.umd.edu/~gasarch/TOPICS/sat/robson.pdf Robson (1986)] | |||
[https://ieeexplore.ieee.org/document/814612 Sch¨oning (1999)] | |||
[https://dl.acm.org/doi/10.5555/314613.314838 Hirsch (1998)] | |||
[https://www.sciencedirect.com/science/article/abs/pii/0020019088900658 Johnson 1988 (1988)] | |||
[http://www.cs.tau.ac.il/~nogaa/PDFS/spectcolpr1.pdf Alon and Kahale (1997)] | |||
| | |||
|- | |||
| rowspan="1" | Polynomial > 3 | |||
| | |||
| | |||
|- | |||
| rowspan="1" | Cubic | |||
| | |||
| | |||
|- | |||
| rowspan="1" | Quadratic | |||
| [https://ieeexplore.ieee.org/document/479412/ Vlasie (1995)] | |||
| | |||
|- | |||
| rowspan="1" | nlogn | |||
| | |||
| | |||
|- | |||
| rowspan="1" | Linear | |||
| [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.4204 Karger, Blum (1997)] | |||
| | |||
|- | |||
| rowspan="1" | logn | |||
| | |||
| | |||
|-|} | |||
Latest revision as of 11:53, 10 October 2022
Problem Description
Graph coloring problem is to assign colors to certain elements of a graph subject to certain constraints.
Vertex coloring is the most common graph coloring problem. The problem is, given m colors, find a way of coloring the vertices of a graph such that no two adjacent vertices are colored using same color. The other graph coloring problems like Edge Coloring (No vertex is incident to two edges of same color) and Face Coloring (Geographical Map Coloring) can be transformed into vertex coloring.
Bounds Chart
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | [- Brute-force search (1852)]
Beigel & Eppstein; 1995 (1995) |
|
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | Vlasie (1995) | |
| nlogn | ||
| Linear | Karger, Blum (1997) | |
| logn |