Graph theory and combinatorics
Provisional editorial order for Top Open Problems: Millennium Prize Problems first, followed by assessed difficulty tiers; the unassessed remainder keeps its previous catalogue order. About rankings
Browse by subject
Search this collection by problem ID, title, classification, subject, provider, or model.
Search results
No matching problems. Try another search or clear a filter.
93 records · Search and filter
- Math-4534 Resolution Lower Bounds for Clique Certification
- Math-4539 Local Approximation of Random-Graph Semidefinite Programs
- Math-4545 Hardness of Root-Dependent Spanning-Tree Optimization
- Math-4546 Hardness of Path-Cost Arborescence Optimization
- Math-4548 Degree-Utility Optimization in Graphs
- Math-4557 Sample Complexity of Vertex-Distribution-Free Graph Testing
- Math-4565 Complexity of Submodular $k$-Partition
- Math-4568 Arborescences Induced by Linear-Programming Pivot Rules
- Math-4572 Better-Than-Two Approximation for Multiplicative Connectivity Augmentation
- Math-4574 Compact Representations of Four-Thirds Near-Mincuts
- Math-4575 Better Approximations for Unrelated Graph Balancing
- Math-4576 Deterministic Optimization of Top-$k$ Perfect-Matching Edges
- Math-4578 Algebraic and Graph-Property Tests for Quantum Functions
- Math-4584 LOCAL Coloring Complexity and Constant-Round Decidability on Trees
- Math-4586 Determinacy Methods in LOCAL and Borel Coloring
- Math-4593 Convex Relaxations for Planted Graph Matching
- Math-4612 Near-Linear Subgraph Isomorphism for Acyclic Patterns
- Math-4622 Approximating Fare-Zone Assignment on Trees
- Math-5023 Vertex flattenings generate the phylogenetic ideal
- Math-5056 Dominating sets as marked centralizer covers in graph groups
- Math-5161 Duplicate Planar Min-Bisection and Bicriteria Extraction
- Math-5162 Duplicate Bicriteria Spanning-Tree Enumeration
- Math-5193 Capacity-Preserving Conversion to Unsplittable Flows
- Math-5207 Composite Repetition of Three Matroid Questions
- Math-5212 Polynomial Freiman–Ruzsa Conjecture over Binary Vector Spaces
- Math-5221 Combinatorial Decompositions of the All-Ones Vector
- Math-5250 Defining High-Dimensional Expanders Through Local Spectra
- Math-5254 Restricted Models of Vertex-Distribution-Free Testing
- Math-5267 Unspecified Combinatorial Optimization Problem
- Math-5268 Half-Integral Extreme Points for Feedback Vertex Set
- Math-5269 Approximating Submodular Functions by Matroid Rank Functions
- Math-5278 Open Problems in Local Graph Complexity
- Math-5284 Unspecified Flag Algebra Extremal Problem
- Math-5290 Stable Algorithms and Overlap Gaps for Friendly Bisections
- Math-5299 Average-Case Complexity of Clique on Sparse Graphs
- Math-5300 Spreadness as a Replacement for Sunflower Structure
- Math-5307 Mixing of Random Colorings on General Graphs
- Math-5316 Workshop Contents Listing for Combinatorial Optimization
- Math-5319 Duplicate Fare-Zone Approximation Question
- Math-5320 Two-Coloring Light Tournaments
- Math-5321 Duplicate Light-Tournament Two-Coloring Question
- Math-5322 Half-Integral Extreme Points for a Feedback-Vertex-Set Relaxation
- Math-5323 Duplicate Fiorini Feedback-Vertex-Set Question