EGRES maintains a web-site on open problems related to the research area
of the group. This site is intended to be more than just a problem collection,
we plan to continuously add new informations and comments supplied by
researchers who work on similar topics.

If you have any comments or observations about a problem, please send it
in email to Jácint Szabó (jacint@elte.hu). You can submit it either
in Latex or in Text format; new bibliographical information, links to web
pages or online papers are also greatly appreciated. Please indicate in the
title the number of the problem your comment refers to. We will add any
relevant new information as a separate entry to the page of the problem.

We also welcome the submission of open problems that are related to our
field of research. The problems that we find relevant to the group's work
will be added to this web-site.

This page lists the problems by topics. A full list of all problems by
problem numbers is also available here. You
can also download the full texts of the problems in postscript or PDF format.

## Colorings

1. When does the list coloring theorem hold for the intersection of two matroids?
24. Berge's conjecture on path partitions
## Connectivity

2. Is there an analogue of Nash-Williams' strong orientation theorem for hypergraphs?
3. Characterization of graphs that have a k-connected orientation
4. Di-Eulerian orientations that remain k-edge-connected after the deletion of any single node [SOLVED]
5. Transforming a k-edge-connected orientation into a k-connected one [SOLVED]
6. Parity-constrained strongly connected orientations
7. Constructive characterization of (k,l)-edge-connected digraphs [SOLVED]
8. Incomplete splitting-off in digraphs
12. Woodall's conjecture
13. Vertex-connectivity augmentation of digraphs [SOLVED]
15. Covering in-deficient sets by nodes [SOLVED]
16. Disjoint Steiner-trees
18. Making the union of two directed spanning trees strongly connected
19. Union of a spanning arborescence and a directed spanning tree
28. Vertex disjoint circuits in Eulerian digraphs
29. Smooth well-balanced orientations with prescribed in-degrees
30. Decomposing rooted (k,l)-connected graphs into rooted k-connected parts
31. Bush-conjecture
34. Super source-super sink connected digraphs
## Constructive characterization

7. Constructive characterization of (k,l)-edge-connected digraphs [SOLVED]
38. Acyclic digraphs with prescribed sized minimum cuts
## Graph theory

26. Compatible Euler-tours
27. Packing capacity disjoint m-arborescences
28. Vertex disjoint circuits in Eulerian digraphs
31. Bush-conjecture
32. Partitionability to a tree and a spanning tree
33. Strongly edge-disjoint arborescences
35. In-degree bounded arborescences
36. Independent arborescences in acyclic digraphs
37. Red-blue cut problem (RBC)
41. Decomposition into two trees with orientation constraints
42. Covering by k-branchings
## Matchings and parity

9. Perfect path-matching algorithm [SOLVED]
10. Exact matching in red-blue bipartite graphs
11. Characterization of dual-critical graphs
17. Deciding the validity of the score sequence of a soccer tournament
20. Maximum weight k-element subsets of perfect matchings
21. Graphs extendable to a uniquely matchable bipartite graph
22. Bounded minimum weight matching problem
## Matroids and submodularity

1. When does the list coloring theorem hold for the intersection of two matroids?
6. Parity-constrained strongly connected orientations
14. Expressing vectors using bases of a matroid
23. The Aharoni-Berger conjecture
25. Is every matroid 1-smooth?
27. Packing capacity disjoint m-arborescences
39. Destroying rigidity
41. Decomposition into two trees with orientation constraints
## Orientation

2. Is there an analogue of Nash-Williams' strong orientation theorem for hypergraphs?
3. Characterization of graphs that have a k-connected orientation
4. Di-Eulerian orientations that remain k-edge-connected after the deletion of any single node [SOLVED]
5. Transforming a k-edge-connected orientation into a k-connected one [SOLVED]
17. Deciding the validity of the score sequence of a soccer tournament
29. Smooth well-balanced orientations with prescribed in-degrees
## Polyhedra

20. Maximum weight k-element subsets of perfect matchings
21. Graphs extendable to a uniquely matchable bipartite graph
22. Bounded minimum weight matching problem

Last modification: 1.3.2011. Please email your comments to Jácint Szabó!