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