# Category:Open Problems

From Egres Open

This category contains all open problems.

## Pages in category "Open Problems"

The following 97 pages are in this category, out of 97 total.

### A

### B

### C

- 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
- Cyclic stable matchings

### D

- Deciding kernel-perfectness
- Deciding the existence of popular matchings
- 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

### E

### G

### I

### L

### M

- 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

### O

### P

### R

### S

- 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 vertex covers
- Strongly minimal edge cover