graph-theory

  1. PTIME or NP-Hardness of stochastic objective function

  2. Showing hardness of maximizing stochastic objective function over graph
  3. A data structure to answer closest node queries in a weighted tree positively weighted tree

  4. Results/concepts that also proved useful outside of their "home areas"
  5. Is perfect matching for bipartite graph with no cycles unique?

  6. Generating random labelled trees

  7. Is NP-complete the existence of paths of a given length in a directed graph?
  8. Closeness Centrality for Weighted Graphs

  9. Complexity of Dijkstra algorithm in graph with negative weights

  10. Path Finding: single-source, multi-path, multi-target, and max-depth - approaches and application

  11. Number of distinct nodes in a random walk

  12. Realization of a bipolar orientation by a mixed graph

  13. Complexity of bounded degree full contraction

  14. Finding a Minimal k-Subgraph

  15. Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?
  16. Maintain a given maximum independent set after vertex removal, polynomial?
  17. What is the name of a graph with local clustering coefficients equal to zero?

  18. Hardness of Approximation for minimum path cover in an undirected graph?

  19. Counting Isomorphism Types of Graphs

  20. How good of an approximate 2-coloring can you get of the halved cube graph?

  21. Find the maximum induced (weighted) subgraph with edge weights greater than some minimum

  22. Are social networks typically good expanders?
  23. Common insights into hypothetical complexity of graph problems
  24. What is the complexity of this graph problem?

  25. Is Eulerian Path (or Eulerian Cycle) definable in Monadic Second Order Logic?

  26. Partitions of regular graphs with upper bounds on bipartition width
  27. Eigenvalues of adjacency matrix of a connected bipartite graph
  28. Does any DAG can be topologically sorted?
  29. Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$

  30. Minimal Cost of Eulerian Path

  31. Reduce $m$-clause 3SAT to PLANAR-3SAT in $O(m^{2-\varepsilon})$
  32. Maximize graph with k cut edge operations
  33. Are there any 'graphical' algebras that can describe the 'shape' of graphs?

  34. Efficient way to generate random planar cubic bipartite graphs

  35. Practical polynomial-time implementation of bounded degree graph isomorphishm
  36. reference for a special modular decomposition
  37. Digraph game reduction problem
  38. Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

  39. Will core decomposition get a maximal clique?
  40. Complexity of recognizing generalized graph join

  41. Is DAG isomorphism NP-C

  42. Are equally weighted MSTs closely related?

  43. size of the induced matching

  44. Space efficient "industrial" unbalanced expanders
  45. Maximum weight non-overlapping paths in a DAG

  46. Minimum cut on a directed graph with negative term

  47. Why do spectral ultrasparsifiers need to be trees

  48. Counting the number of connected components in a dynamic plane graph

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

  50. Unbalanced connected partition
  51. What are graph grammars?

  52. Is a k-connected graph also k-1 connected?

  53. Bounding size of separators when in-degree/out-degree is small?
  54. Data structure to search name of files and get its path

  55. FOL sentence encoding acyclic graphs using only universal quantifiers
  56. Random Deterministic Automata
  57. Flow Optimization: minimum cost matching of demands from multiple sinks
  58. For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?
  59. Properties of toroidal graph
  60. Common terminology used for lower/upper bounds

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

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

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

  64. Minimum path edge-cover or minimum flow with unit capacities and DAGs
  65. One Generalization of Graph Isomorphism Problem
  66. Determining ties in random network centrality rankings?
  67. Bipartite matching with degree domination

  68. Preference based group generator
  69. Algorithm finding path with maximal ratio of white vertices

  70. Complexity of listing all minimal cut sets / connected 2-partitions of a graph

  71. Application of graph theory in computer science
  72. Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices

  73. Minor and subdivision

  74. Decomposition of edges of eulerian graph into maximum number of cycles

  75. Best Hamiltonian Cycle Problem solver

  76. Graceful labeling completion problems
  77. Optimizing Maximum Weighted Matching (Edmonds Blossom)

  78. Complexity consequence of logarithmic boolean width of co-bounded degree graphs?
  79. Book/ Monograph on graph minor theory [Reference request]
  80. Transitive Closure of Weighted Random Graphs?
  81. The algebraic connectivity of graphs with large isoperimetric number

  82. Finding k shortest Paths with Eppstein's Algorithm

  83. Directed graph with bounded in-deg can be partitioned in a balanced way

  84. Almost regular subhypergraph of hypergraph with large minimal degree

  85. Modifying Edmonds' Blossom Algorithm

  86. Clique cover problem

  87. Graph factors of maximum weight
  88. What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?
  89. Existence of $d$-regular expander graph that can be represented as a bipartite graph
  90. well-behaved outerplanar

  91. reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs?
  92. Counting xyz-graphs in $\mathbb{Z}_n^3$
  93. Lower bound on the largest restrained cubic subset
  94. Graph rewriting with one-to-many pattern matching?

  95. Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$
  96. A conceptual question regarding hardness proofs by reduction
  97. Efficient update of reachable set of a node in a digraph
  98. Graphs for which the number of shortest paths between every pair of vertices is polynomially bounded

  99. Is this vertex ordering optimization NP-Hard?

  100. Graph addition chains