10 problems

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.

Le's induced-path conjecture. There is a constant $c$ such that every $\mathcal{O}_2$-free $n$-vertex graph has at most $n^c$ distinct induced paths.

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

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…

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…

Rainbow induced-path conjecture. For each $r\geq 3$, every properly coloured $K_r$-free graph of chromatic number $\chi$ contains a rainbow induced path of length $\chi^{1/(r-2)}$.

Let $G$ be a graph, and let $P_k$ denote an induced path on $k$ vertices. An induced path $P$ is avoidable if every extension of $P$ is contained in an induced cycle, where an exte…