59 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 $Q_n$ be the graph with vertex set $\{0,1\}^n$ and edges between vertices differing in exactly one coordinate. A path decomposition of $Q_n$ is a pairwise edge-disjoint union o…

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…

Let $P_n=v_1v_2\cdots v_n$ be the path of order $n$, and let $\chi_{lat}(P_n)$ denote its local antimagic total chromatic number, namely the minimum number of distinct vertex weigh…

Path-threshold transfer conjecture. There exists a graph sequence ${\cal G}$ such that

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…

Halfpap–Anastasia conjecture. This lower bound is best possible. The conjecture has already been proved for $n=3,4$ by Johnston, Palmer, and Sarkar, and for $n=5$ by Halfpap and An…

Stein's conjecture. If

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

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

Let $k$ be an integer with $k\geq 3$. A graph is considered in which paths are measured by their length. Kotzig's conjecture. No graph has exactly one path of length $k$ between ev…

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…

For each fixed $k$, define … where $P_n$ is the path on $n$ vertices and $\tilde{r}(P_k,P_n)$ is the online size Ramsey number. The path constants conjecture. … These values refine…

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…

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…

Vito–Silaban's conjecture. For $n\ge 5$ and $m\ge 3$,

ST conjecture. Suppose that (1) $G[S]$ is an $(x,y)$-path $P$ and $T$ is an independent set; (2) every vertex in $S$ has at least one neighbor in $T$; and (3) every vertex in $T$ h…

Longest-path bound-vertex conjecture. Let $G$ be a $k$-connected graph with $k\ge 2$ and let $x,y$ be two distinct vertices of $G$. If $P$ is a longest $(x,y)$-path in $G$, then…

Let $G$ be an $n$-vertex graph, and let $\operatorname{sp}(G,E)$ denote the minimum size of an edge-separating family of paths in $G$. Define … where the maximum is over all $n$-ve…

For graphs $G$ and $H$, let $\tilde{r}(G,H)$ denote the online Ramsey number, and let $K_{1,3}$ be the star with three edges and $P_{\ell}$ the path with $\ell$ vertices. Latip–Tan…

Let $G$ be a graph on $n$ vertices. A strongly-separating path system is a collection of paths in $G$ such that, for every two distinct edges $e$ and $f$ of $G$, there are paths…

The first author's oriented-path conjecture. Every oriented graph $D$ with

Let $N_{\mathcal{P}}(n,H)$ denote the maximum number of copies of a graph $H$ in an $n$-vertex planar graph, and let $P_k$ be the path with $k$ vertices. For fixed $m\geq 2$, with…

Let $P_n$ be a path on $n$ vertices, and let $k\in[2,2(n-1)]$. A magic total labeling is a bijection $f_k:V(P_n)\cup E(P_n)\to[1,2n-1]$. Path $(k,\lambda_k)$-magical total labeling…