ConceptMathematics
Graph coloring
Coloring the nodes of a graph such that no two adjacent nodes share the same color.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Graph theory1Vertices and edges1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
1Lectures that assume it
15The first 12 are shown.
- Graph Theory and Coloring
- Communication Networks
- Cryptography: Encryption
- The Complexity Class NP
- Reductions
- The Role of Computer Assistance in Mathematical Proofs
- Extremal Combinatorics Meets Algorithms and Data Structures
- Strange Gaps in the Local Time Hierarchy
- Algorithms for Bounded Treewidth
- Dinur's Proof of the PCP Theorem: Outline
- Mathematics and Computation: The Landscape of P vs. NP
- Problems in P
Connections
21The lectures that define it or assume it, and the concepts next to it.
Lectures16
- The Importance of Mathematics
- Graph Theory and Coloring
- Communication Networks
- Cryptography: Encryption
- The Complexity Class NP
- Reductions
Show 10 moreShow fewer
- The Role of Computer Assistance in Mathematical Proofs
- Extremal Combinatorics Meets Algorithms and Data Structures
- Strange Gaps in the Local Time Hierarchy
- Algorithms for Bounded Treewidth
- Dinur's Proof of the PCP Theorem: Outline
- Mathematics and Computation: The Landscape of P vs. NP
- Problems in P
- Nondeterminism
- Elementary Embeddings and Small Large Cardinals
- Dinur's PCP Theorem: Degree-Reduction, Expanderizing, and Mini-PCP