graph-theory

  1. Are equally weighted MSTs closely related?
  2. size of the induced matching
  3. Space efficient "industrial" unbalanced expanders

  4. Maximum weight non-overlapping paths in a DAG

  5. Minimum cut on a directed graph with negative term
  6. Minimal Cost of Eulerian Path

  7. Why do spectral ultrasparsifiers need to be trees
  8. Counting the number of connected components in a dynamic plane graph

  9. An alternative formulation of max flow problem

  10. Why isn't the Charikar algorithm for finding the densest subgraph optimal?

  11. Unbalanced connected partition

  12. What are graph grammars?

  13. How can i draw a general resource graph which cannot be completely reduced but which is free from deadlock?
  14. Is a k-connected graph also k-1 connected?

  15. Bounding size of separators when in-degree/out-degree is small?
  16. Vertex deletion to perfect matching

  17. Data structure to search name of files and get its path

  18. FOL sentence encoding acyclic graphs using only universal quantifiers

  19. Random Deterministic Automata

  20. Flow Optimization: minimum cost matching of demands from multiple sinks
  21. For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

  22. Properties of toroidal graph
  23. Common terminology used for lower/upper bounds

  24. Is there any good and free Introduction to topological graph theory

  25. Girth of graphs that decompose into two disjoint union of spanning trees

  26. Complexity of finding semi-ordered Eulerian tours in a 4-regular graph

  27. Minimum path edge-cover or minimum flow with unit capacities and DAGs

  28. One Generalization of Graph Isomorphism Problem
  29. Determining ties in random network centrality rankings?
  30. Bipartite matching with degree domination

  31. Preference based group generator

  32. Algorithm finding path with maximal ratio of white vertices
  33. Complexity of listing all minimal cut sets / connected 2-partitions of a graph
  34. Application of graph theory in computer science

  35. Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices
  36. Minor and subdivision
  37. Decomposition of edges of eulerian graph into maximum number of cycles

  38. Best Hamiltonian Cycle Problem solver

  39. Graceful labeling completion problems
  40. Optimizing Maximum Weighted Matching (Edmonds Blossom)

  41. Complexity consequence of logarithmic boolean width of co-bounded degree graphs?
  42. Book/ Monograph on graph minor theory [Reference request]

  43. Transitive Closure of Weighted Random Graphs?

  44. The algebraic connectivity of graphs with large isoperimetric number
  45. Finding k shortest Paths with Eppstein's Algorithm
  46. Directed graph with bounded in-deg can be partitioned in a balanced way

  47. Almost regular subhypergraph of hypergraph with large minimal degree

  48. Modifying Edmonds' Blossom Algorithm

  49. Clique cover problem
  50. Graph factors of maximum weight

  51. What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?

  52. Existence of $d$-regular expander graph that can be represented as a bipartite graph
  53. well-behaved outerplanar

  54. reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs?
  55. Counting xyz-graphs in $\mathbb{Z}_n^3$
  56. Lower bound on the largest restrained cubic subset

  57. Graph rewriting with one-to-many pattern matching?
  58. Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$
  59. A conceptual question regarding hardness proofs by reduction

  60. Efficient update of reachable set of a node in a digraph
  61. Graphs for which the number of shortest paths between every pair of vertices is polynomially bounded

  62. Is this vertex ordering optimization NP-Hard?
  63. Graph addition chains

  64. How to partition a graph while minimizing the count of intra-edges?

  65. limit the total flow for some edges in an directed graph
  66. Pathwidth of planarized drawing of $K_{3,n}$

  67. Hadwiger number under matching contraction
  68. Increasing the capacity to maximize the min cut
  69. Vertex Cover applications in the real world

  70. Log space algorithms for modular decomposition tree
  71. Reachability in Dynamic Line Graph

  72. Maximal non-reducible vertex cover of a graph
  73. Vertex isoperimetric number of a graph - NP-hard?

  74. Can a flow be decomposed in a given number of paths?
  75. Is there a name for graph regions that lie between two nodes?
  76. Path-width and chromatic number

  77. Can Lexicographic BFS be implemented in logspace?

  78. How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming?
  79. What is the connection between moments of Gaussians and perfect matchings of graphs?
  80. Automata : Language Containment, Minimality & Graph Homomorphism

  81. Hard extendability problems

  82. Which are the features of network based on eigenvalue distribution?
  83. Optimal polynomial time algorithm to determine if a random graph is $k$-colorable
  84. An edge partitioning problem on cubic graphs

  85. Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

  86. Intractability of restricted decomposition of connected bridgeless cubic graphs
  87. Non-backtracking paths and the zeta function of graphs

  88. A generalization of edge cover

  89. Embedding a graph with specified edge lengths in d-dimensional space
  90. CSPs with unbounded fractional hypertree width
  91. Are there interesting graph classes where the treewidth is hard (easy) to compute?

  92. Looking for a list of algorithms that are more efficient for an outerplanar graph than for an arbitrary graph
  93. Number of solutions to the biclique cover problem

  94. Computing mTSP in a k-complete weighted graph

  95. What is "Synthetic Network" in Network Science?
  96. What can i learn about a graph about which only certain properties are known

  97. Combinatorial Independent set Algorithms for sub-classes of perfect graphs

  98. Connectivity of a random regular graph of degree $d$
  99. Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

  100. Any fast algorithm for minimum cost feedback arc set problem?