Open problems in Graph Theory

Given a single-source fractional flow x meeting demands d_i (D = max_i d_i), is there always an unsplittable routing y that is simultaneously congestion-good (y_a ≤ x_a + D on every arc) and cost-good (cᵀy ≤ cᵀx for every nonnegative cost c)? The congestion half alone is the proven Dinitz–Garg–Goemans theorem (1999); the simultaneous cost strengthening is Goemans' conjecture (Conjecture 1.3 in the SSUF literature).

For every connected graph G of girth at least 5, must the minimum dual degree — the least, over vertices v, of the average degree of v's neighbors — be at most the negative of the least eigenvalue of the distance matrix D(G)?

Every digraph on n vertices with minimum out-degree r contains a directed cycle of length at most ⌈n/r⌉.

If n cliques, each on n vertices, pairwise share at most one vertex, their union can be properly colored with n colors.

In every finite union-closed family of sets (other than {∅}), some element belongs to at least half of the sets.

k runners with pairwise distinct constant speeds circle a unit track from a common start. The conjecture: each runner is, at some moment, at circular distance at least 1/k from every other runner.

How many points can be placed in an n×n grid with no three collinear? At most 2n (two per row), and 2n is achieved for all n up to at least 46 — but conjecturally only ~1.814n is possible for large n.