128 problems

Let $T$ be a tree, and consider the equivalence class of $T$ under mutual embeddability, whose elements are counted up to isomorphism. Tree Alternative Conjecture. The number of is…

Let a graph be well-quasi-ordered (WQO) under the minor relation when every infinite sequence of graphs contains two graphs such that an earlier one is a minor of a later one. Thom…

Andreae's ubiquity conjecture. Every locally finite graph is ubiquitous.

Diestel's conjecture. The Freudenthal compactification of $G$ contains a circle through all vertices and ends of $G$.

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

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.

Let $G$ be a graph, and let $\rho(G)$ denote its maximum capture time, called a CR-ordinal when it occurs as $\rho(G)$ for some graph. Bonato, Gordinowicz and Hahn showed that ever…

Georgakopoulos's conjecture. The line graph of every 4-edge-connected graph has a Hamiltonian circle.

Triangle condition conjecture. One has $\nabla_{p_c}<\infty$.

Let $D=(V,A)$ be a possibly infinite directed graph. An independent set is a set containing no pair joined by a directed edge. A quasi-kernel of a digraph is an independent set $K$…

Let $D$ be an arbitrary large digraph, and let a path-system be a family of pairwise edge-disjoint directed paths, while a cover is a set of edges meeting every directed path under…

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

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…

Let $c\ge m\ge 1$ be integers. Let $P(c,m)$ assert that every exact $c$-coloring of the edges of a complete countably infinite graph—that is, a coloring using all $c$ colors at lea…

Flame extension conjecture. Every $I\ind4a2(D)$ is included in a flame of $D$.

Let $P_\infty$ be the two-way infinite path with vertex set $\mathbb{Z}$, and let $P_\infty \boxtimes P_\infty$ be the infinite diagonal grid with vertex set…

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 the hexagonal grid be the infinite 3-regular graph whose vertices and edges arise from a tiling of the plane by regular hexagons. Consider the virus-containment process in whic…

In an infinite graph, an orientation assigns a direction to each edge. For vertices $u$ and $v$, compare the number of directed paths from $u$ to $v$ with the number of undirected…

The cycle–quadruple conjecture. The following statements are equivalent: if $H$ is the induced subgraph of $G$ with vertex set $X$, then $H$ is a cycle; and the points of $X$ can b…

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…

Let $D$ be a directed graph. For a cut of $D$, consider the cardinalities of the edges crossing the cut in each of the two directions. Thomassen's conjecture. The edges of $D$ can…