64 problems

Hamilton-circle conjecture. The graph $G$ has a Hamilton circle if every ball of radius $2$ in $G$ is 2-connected and

Let $G$ and $H$ be non-isomorphic graphs. We call $H$ a twin of $G$ if there are embeddings $G\to H$ and $H\to G$, that is, injective maps $V(G)\to V(H)$ and $V(H)\to V(G)$ preserv…

Large flame extension conjecture. In every $r$-rooted digraph $D$, every flame extends to a large flame. In particular, every $r$-rooted digraph $D$ admits a large flame.

Salia's conjecture. If $G$ has the double Hall property, then for every $X\subseteq A$ with $|X|\geq 2$ there is a cycle $C_X$ in $G$ such that

A majority $2$-vertex-coloring of a graph is a coloring of its vertices with two colors such that, at every vertex, the number of neighbors having the same color is at most the num…

Strict $q$-to-$q$ threshold conjecture. For every $q\in(1,\infty)$,

Loose weighted-web conjecture. A loose weighted web is linkable.

Let $\mathcal F$ be the class of graphs $G$ such that no component of $G$ contains every finite graph as a minor. A graph $U$ is $<$-universal for a class if every graph in the cla…

Let $G$ be a locally finite tree. A graph $G$ is reconstructible if every graph hypomorphic to $G$ is isomorphic to $G$, where hypomorphism means that there is a bijection between…

Let $\Gamma$ be a web, and let $A$ and $B$ be its distinguished vertex sets. An $A$--$B$-separating set $S$ meets every $A$--$B$ path; $S$ is linkable into $A$ in…

Ultra-fat half-grid conjecture. Every connected, quasi-transitive, locally finite graph with a thick end contains an ultra-fat model of the half-grid.

Aanderaa–Karp–Rosenberg conjecture. Every nontrivial monotone graph property is elusive.

Halin's ray graph conjecture. Every graph admits a ray graph for each of its ends.

Let the Pentagon Graph be the infinite graph obtained from a pentagonal tiling of the plane, with vertices of degrees three and four. Consider the virus-containment process in whic…

Let $G$ be a nonempty connected graph. Write $V(G)$ for its vertex set and $d_G$ for its geodesic distance. Let $\mathfrak{MB}$ denote the class of metric spaces $(X,d)$ such that…

Multigraph non-3-colorability conjecture. There exists an undirected countable multigraph that is not majority 3-colorable.

A majority $3$-edge-coloring of a graph is an edge-coloring with three colors in which, at every vertex, the number of incident edges of its most frequent color is at most the numb…

Let $D$ be a digraph without infinite directed paths. Infinite Gallai–Milgram conjecture. There is a vertex-partition $d4ab$ of $D$ into directed paths and an independent set $U$ o…

Consider theorems about finite combinatorial structures that admit proofs by augmenting paths. Augmenting-path meta-conjecture. Such theorems should remain true in a structural for…

Erdős–Hajnal–Soukup partition conjecture. There is a partition

Upper-density conjecture. For every integer $k\geq 3$, every $k$-edge-colouring of $K_{\mathbb{N}}$ contains a monochromatic path $P$ such that

Let $T$ be an infinite tree with bounded degree. Define $f(T)$ by removing all end-paths of $T$ except the end-branches, and for $n\geq 2$ set $f^n=f^{n-1}\circ f$. A path may be i…

A graph $G$ is $d$-degenerate if it has an ordering of its vertices $v_1,v_2,\ldots$ such that … for every $i\geq 1$. The upper density of a set $V\subseteq\mathbb N$ is…

Mader's internally-disjoint-path conjecture. Such a system $\mathcal{P}$, set $X$, and partition $\mathcal{Y}$ exist.

Gallai's conjecture. There exists such a system $\mathcal{P}$ and set $X$.