List of open problems
From Egres Open
This is the alphabetical list of all open (and solved) problems on the website.
- Click here for the list of problems sorted by categories.
- To see the open problems in a specific category, click on the name of the category on the left sidebar.
Solved problems
- Characterization of graphs having a k-connected orientation
- Characterizing integral g-polymatroids
- Cyclic stable matchings
- Deciding the existence of popular matchings
- Decomposition into forests and a bounded-degree subgraph
- Decomposition into two trees with orientation constraints
- Edge-disjoint spanning trees and paths
- Edge-disjoint T-connectors
- Existence of completely stable flow
- Expressing vectors using bases of a matroid
- Finding a 2-way stable 3-way exchange
- Finding the largest popular matching in a bipartite graph
- Graphs extendable to a uniquely matchable bipartite graph
- In-degree bounded directed forests
- Maximizing a skew-supermodular function
- Maximum size of a source-sink reorientable set
- Node disjoint circuits in Eulerian digraphs
- Partial vertex cover in bipartite graphs
- Partitionability to a tree and a spanning tree
- Skew-supermodular colouring with prescribed class-sizes
- Skew-supermodular list colouring
- Small representations of gammoids
- Strongly edge-disjoint arborescences
- Union of a spanning arborescence and a directed spanning tree
- Well-balanced orientations of hypergraphs
Open problems
- Achieve global rigidity by pinning nodes
- Acyclic orientation with connectivity prescriptions
- Acyclic orientation with parity constraints
- Aharoni-Berger conjecture
- Are t-perfect graphs strongly t-perfect?
- Are there deletion-contraction formulas for the polymatroid Tutte polynomial?
- Berge's conjecture on path partitions
- Binary matroid representation of cyclic families
- Bounded degree matroid basis
- Caccetta-Häggkvist conjecture
- Capacitated packing of k-arborescences
- Changing conservative weightings in bipartite graphs
- Chromatic number of t-perfect graphs
- Compactness of Kőnig-property
- Compatible Euler-tours
- Complexity of computing a v-reduced divisor in multigraphs
- Complexity of computing the rotor-router action
- Complexity of the chip-firing reachability problem for general digraphs
- Complexity of the halting problem for Eulerian multigraphs
- Complexity of the halting problem for simple digraphs
- Conforti-Cornuéjols conjecture on the MFMC property
- Constructive characterization of dumpy graphs
- Covering a crossing supermodular function with graph edges
- Covering a crossing supermodular function with pairwise non-parallel arcs
- Covering a symmetric crossing supermodular function with hyperedges of prescribed size
- Cyclic orderings of matroids
- Deciding kernel-perfectness
- Deciding the validity of the score sequence of a soccer tournament
- Decomposing rooted (k,l)-connected graphs into rooted k-connected parts
- Decomposition of oriented k-partition-connected digraphs
- Destroying rigidity
- Disjoint spanning in- and out-arborescences
- Disjoint strongly connected spanning subgraphs
- Edge-covering number of 2-polymatroids
- Edge-independent spanning trees
- Equitability of matroids
- Equitable list colouring
- Exact matching in red-blue bipartite graphs
- Extreme direction Sperner for square 0-1 matrix
- Finding kernels in special digraphs
- Fishbone conjecture
- Generic global rigidity in three dimensions
- Generic rigidity in three dimensions
- Goddyn's conjecture on thin spanning trees
- Gonality and edge subdivisions
- Head-disjoint strongly connected orientations
- Highly element-connected orientation
- Incomplete splitting-off in digraphs
- Independent arborescences in acyclic digraphs
- Independent trees
- Infinite Lucchesi-Younger
- Integer decomposition of smooth polytopes
- Kriesell's conjecture
- List colouring of two matroids
- Local edge-connectivity augmentation of a hypergraph with fixed rank
- Making the union of two directed spanning trees strongly connected
- Maximum square-free 2-matching
- Maximum weakly stable matchings in graphs without odd preference cycles
- Maximum weight bounded fractional matching
- Maximum weight k-element subsets of perfect matchings
- Min-sum two edge-disjoint paths
- Minimum k-way cut in a hypergraph
- Minimum polychromatic number for plane graphs with fixed girth
- Opposite vertices of base polyhedra
- Orientation conjecture of Nash-Williams
- Orientation of nonideal clutters
- Orientation with shortest round trip
- Orientation-compatible w-vertex cover
- Parity constrained strongly connected orientations
- Partition median problem
- Partitioning a bipartite graph into proportional factors
- Polyhedral description of kernels
- Quasi-kernels and quasi-sinks
- Rainbow matchings in bipartite graphs
- Rank-respecting augmentation of hypergraphs with negamodular constraints
- Recognition of Seymour graphs
- Red-blue cut problem
- Rota's conjecture on disjoint bases
- Rotor-routing halting problem
- S-T edge-connectivity augmentation
- Sabidussi's compatibility conjecture
- Scrambled Rota conjecture
- Serial symmetric exchanges
- Seymour's self-minor conjecture
- Skew-supermodular colouring with two class sizes
- Small quasi-kernels in directed graphs
- Smooth well-balanced orientations with prescribed in-degrees
- Sparsifier subgraphs
- Strong colouring of matroid-graph pairs
- Strongly maximal H-free spanning subgraph
- Strongly maximal matchings
- Strongly minimal edge cover
- Upper bound on common independent set cover
- Upper bound on the divisorial gonality of a graph
- Weighted bipartite edge colouring
- Well-balanced orientations of hypergraphs
- Woodall's conjecture
