13 problems

A graph is properly colored if adjacent vertices receive distinct colors, and a vertex-colored graph is rainbow if no two vertices have the same color. A graph is triangle-free if…

Beisegel et al.'s conjecture. For every positive integer $k$, every graph that contains an induced $k$-vertex path also contains an avoidable induced $k$-vertex path.

Let $G$ be a finite simple graph, and write $|G|$ for its number of vertices. Two subgraphs are anticomplete if their vertex sets are disjoint and no edge joins the two vertex sets…

Induced-path conjecture. There is a positive constant $c(k)$ such that the graph contains an induced path on

For $a,b\in\mathbb{N}$, let $K_{a,a}$ be the complete bipartite graph with $a$ vertices in each part, and let the $b$-vertex path be the path with $b$ vertices. Dallard–Krnc–Kwon–M…

Let $G$ be a finite simple triangle-free graph, let $\chi(G)$ be its chromatic number, and let $\phi:V(G)\to[k]$ be a proper vertex coloring, where $k=\chi(G)$. A path in $G$ is ra…

Many-path Menger-type conjecture. There exists a constant $c$ such that, for all such $G$, $X$, $Y$, $d$, and $k$, either there exist $k$ disjoint $X-Y$ paths $P_1,\dots,P_k$ satis…

Let $k\in\mathbb{N}$, and let $G$ be a $k$-degenerate graph with a path of order $n\geq 1$. An induced path is a path whose vertices induce exactly the edges of the path in $G$. Es…

Two-edge rooted-path conjecture. The two-rooted path $(P,s,t)$ is inherent.

Esperet's conjecture. There is a constant $d$ such that every $k$-degenerate graph that has a path of order $n$ also has an induced path of order at least

Erdős's size-Ramsey conjecture.

Beisegel–Chudovsky–Gurvich–Milanič–Servatius conjecture. If $G$ contains an induced path on $k$ vertices, then $G$ contains an avoidable induced path on $k$ vertices.

Linear-logarithmic induced-path conjecture. There is some constant $c>0$ such that every triangle-free graph of chromatic number $\chi$ contains an induced path of length at least…