34 problems

Let $G$ be an oriented graph, and let $4\delta^0(G)4$ denote its minimum semidegree, the minimum of the in-degree and out-degree over all vertices. An oriented path of length…

Let $M(H,n)$ be the minimum number of monochromatic copies of a graph $H$ in a red/blue coloring of $K_n$, and define the threshold Ramsey multiplicity by … where $r(H)$ is the Ram…

Let $n$ be a positive integer, and let $\ell\geq 2$ be fixed. Consider graphs on $2n+1$ vertices, and say that two vertices are joined by a path of length $2\ell+1$ when such a pat…

Stein's conjecture. If

Let $k_1\geq k_2\geq\ldots\geq k_m\geq 3$ with $k_1>3$, and let … be the disjoint union of paths. For integers $n\geq m\geq 3$, write $c(n,a,b)$ and $c(n,a)$ as in the preceding de…

Path $P_6$ edge-inducibility conjecture. The lower bound is exact:

Edge inducibility conjecture for odd paths. If $k\geq 5$ is odd, then

For odd $k\geq5$, let $H_{n,k}$ be the graph obtained from a clique $K_{\lfloor k/2\rfloor}$ by choosing a vertex $v$, adding $m$ independent vertices adjacent to $v$, and adding…

Let $D$ be a digraph, and call a set of vertices independent if no two of its vertices are joined by an arc. A path in $D$ is longest if it has maximum length among all paths in…

Let $P_n$ be the path on $n$ vertices, and let $\gamma_e(P_n)$ denote its extended irregular domination number. Path-domination conjecture. For $n\geq 4$, … The equality is known f…

Babai spectrum conjecture for paths. Under these hypotheses,

Let $G$ be a graph on $n$ vertices. A path separating system of $G$ is a collection of paths in $G$ such that, for every ordered pair of distinct edges $(e,f)$, some path contains…

Cyman–Dzido–Lapinskas–Lo conjecture. For every fixed $k \geq 5$,

Cyman–Dzido–Lapinskas–Lo conjecture. For every $n\geq 4$,

Let $P_n$ denote the path on $n$ vertices, and let $r(P_n,P_n)$ be its two-color Ramsey number. Set … where $n$ is sufficiently large. A graph arrows $(P_n,P_n)$ when every 2-edge-…

López-Bracho et al.'s robust coloring conjecture. There exists a $3$-coloring of $G$ such that the number of monochromatic edges of $H$ is at most

Pendant-path conjecture. The pendant path graph $P_n^*$ is $r$-EKR whenever

For positive integers $n>d\geq k$, let $\phi(n,d,k)$ be the smallest integer such that every $n$-vertex graph with at least $\phi(n,d,k)$ vertices of degree at least $d$ contains a…

Hippchen's conjecture. Any two longest paths in $G$ share at least $k$ vertices.

Let $A$ be a finite abelian group, and let $\mathbb{P}$ be the class of path graphs. A group is weakly $\mathbb{P}$-cordial if all but finitely many path graphs are $A$-cordial. We…

Let $A$ be a finite abelian group, and let $\mathbb{P}$ be the class of path graphs. A group is $\mathbb{P}$-cordial if every path graph is $A$-cordial, where $A$-cordiality means…

Let $P_k$ be a path of length $k$, and let $f(n,P_k)$ denote the maximum number of copies of $P_k$ in a planar graph on $n$ vertices. Even-length path conjecture. For every positiv…

Let $G$ be a 2-connected graph on $n$ vertices, and let $x,y\in V(G)$. Let $0<\alpha\leq\frac{1}{2}$. Alpha-generalized path conjecture. If $G-\{x,y\}$ contains more than…

For a digraph $D$, define the semidegree of a vertex by $d^0(v):=\min\{d^-(v),d^+(v)\}$ and the minimum semidegree by $\delta^0(D):=\min\{d^0(v):v\in V(D)\}$. Minimum-semidegree pa…

Let $P_k$ denote the path with $k$ vertices, and let $G$ be a graph on $3n-1$ vertices. Schelp's conjecture. If $n$ is sufficiently large and … then $G$ arrows $P_{2n}$, meaning th…