A simple algorithm for 4-coloring 3-colorable planar graphs (Q974757): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2010.02.015
+Normal rank
@@ Property / OpenAlex ID @@
+W2109639734
@@ Property / OpenAlex ID: W2109639734 / rank @@
+Normal rank
@@ Property / cites work @@
+Every planar map is four colorable. I: Discharging
+Normal rank
@@ Property / cites work @@
+Every planar map is four colorable. II: Reducibility
+Normal rank
@@ Property / cites work @@
+New approximation algorithms for graph coloring
@@ Property / cites work: New approximation algorithms for graph coloring / rank @@
+Normal rank
@@ Property / cites work @@
+An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
+Normal rank
@@ Property / cites work @@
+Conditional hardness for approximate coloring
@@ Property / cites work: Conditional hardness for approximate coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Subgraph Isomorphism in Planar Graphs and Related Problems
+Normal rank
@@ Property / cites work @@
+Zero knowledge and the chromatic number
@@ Property / cites work: Zero knowledge and the chromatic number / rank @@
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Efficient Planarity Testing
@@ Property / cites work: Efficient Planarity Testing / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate graph coloring by semidefinite programming
+Normal rank
@@ Property / cites work @@
+Q2726740
@@ Property / cites work: Q2726740 / rank @@
+Normal rank
@@ Property / cites work @@
+The four-colour theorem
@@ Property / cites work: The four-colour theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Improving the performance guarantee for approximate graph coloring
+Normal rank