Uploaded April 2018 | Updated September 2026, 15 minutes ago
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html
Specific topics covered in this lecture: bounded-degree graph colorability, NP-completeness of max-degree-4 graph colorability, degree-reduction "gadgets", 3-colorability constraint-propagation, local replacement of nodes by super-gadgets, threshold of intractability, 2-colorability, odd cycles, infinite graphs, chromatic numbers, membership-preserving transformations, planar graphs, Kuratowski's theorem, planarity-preserving gadgets, NP-completeness of 3-coloring planar graphs, composing reductions, 3-colorability of planar max-degree-4 graphs is NP-complete, searching for smaller / simpler gadgets, Four-Color Theorem, graph-colorability on tori
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html
Specific topics covered in this lecture: bounded-degree graph colorability, NP-completeness of max-degree-4 graph colorability, degree-reduction "gadgets", 3-colorability constraint-propagation, local replacement of nodes by super-gadgets, threshold of intractability, 2-colorability, odd cycles, infinite graphs, chromatic numbers, membership-preserving transformations, planar graphs, Kuratowski's theorem, planarity-preserving gadgets, NP-completeness of 3-coloring planar graphs, composing reductions, 3-colorability of planar max-degree-4 graphs is NP-complete, searching for smaller / simpler gadgets, Four-Color Theorem, graph-colorability on tori
