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ó!