51 problems

An oriented graph is a directed graph with at most one directed edge between any pair of vertices. For an oriented graph $G$, let $V(G)$ be its vertex set, let $n=|V(G)|$, and writ…

Let $H$ be a 3-graph of order $n$, let $sigma_2(H)$ be the minimum of $deg(u)+deg(v)$ over adjacent vertices $u,v$, and let $H_{n,s}^2$ be the corresponding extremal 3-graph. Zhang…

Darbinyan's degree conjecture. If $p-1$ vertices in $V(D)$ have degrees at least $p$, then $D$ contains a Hamiltonian bypass.

Fujita–Kawarabayashi conjecture. There is a least non-negative integer $f_k(m)$ such that every $k$-connected graph $G$ with

DeBiasio's conjecture. Every $n$-vertex digraph $D$ satisfying

Benhocine–Wojda degree-sum conjecture. If the sum of the degrees of every two nonadjacent vertices is at least $2p-1$, then $D$ contains $D(n,2)$ for each $n\in[3,p]$, except for c…

Degree-sum conjecture for Hamiltonian bypasses. If, for every distinct pair of nonadjacent vertices $x,y$ and $w,z$,

A digraph $D$ has order $n\ge 3$. A pair of nonadjacent vertices is dominated if it has a common in-neighbor, and dominating if it has a common out-neighbor. Let $d(u)$ denote the…

Let $G$ be a claw-free graph, meaning that $G$ has no induced subgraph isomorphic to $K_{1,3}$. Let $\delta(G)$ denote its minimum degree and let $\alpha(G)$ denote its independenc…

Let $D$ be an oriented graph on $n\ge 3$ vertices. For distinct vertices $u,v$, call them non-adjacent if neither directed arc joins them, and define … when $D$ has a pair of non-a…

Let $D$ be an oriented graph on $n\ge 3$ vertices with minimum degree $\delta$. For vertices $u,v$, write $d(u)$ and $d(v)$ for their degrees, and call them non-adjacent if neither…

Let $H$ be a 3-graph of order $n$, let $sigma_2(H)$ denote the minimum $deg(u)+deg(v)$ over adjacent vertices $u,v$, and let $H^{1,2}_{n,x,y}$ be the construction defined in the so…

Let $G$ be a graph with maximum degree $\Delta$ and minimum degree $\delta$. Magnant et al.'s degree-based path-cover conjecture. The graph $G$ needs at most … paths to cover its v…

Let $D$ be a 2-strong digraph, meaning that deleting any one vertex leaves a strong digraph, and let $D$ have order $n$. Suppose that $n-1$ vertices of $D$ have degrees at least…

Minimum vertex-degree conjecture. For every $\varepsilon>0$ and every fixed bound on $\Delta_1(T)$, every sufficiently large $3$-graph $H$ with

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…

Let $G$ be a 2-connected graph of order $n$. Li's conjecture. If the number of vertices of degree at least $k$ is at least … then $G$ has a cycle of length at least $2k$. The paper…

Let $G$ be a 2-connected graph on $n$ vertices. Häggkvist–Jackson conjecture. If $G$ contains at least … vertices of degree at least $k$, then $G$ has a cycle of length at least ……

Bermond's conjecture. If at least one of these conditions holds for every pair $x_i,x_j$ with $i<j$, then $c(G)\geq c$. Bermond proposed this conjecture as a generalization of clas…

Czygrinow–Kierstead–Molla's conjecture. If $\delta^0(D)\geq 2k$, then $D$ contains $k$ vertex-disjoint directed triangles.

Wang's conjecture. If $\delta(W)\geq (3n-3)/2$, then $D$ contains an arbitrary $W$-cycle-factor.

Wang's conjecture. If $\delta^0(D)\geq (9k-3)/4$, then $D$ contains $k$ vertex-disjoint directed cycles, each of order at least $3$.

Wang's conjecture. If $|W|\geq 3k$ and $\delta(W)\geq 2n/3$, then $G$ contains an arbitrary $W$-cycle-factor.

Bang-Jensen et al.'s conjecture. If

Matsuda's conjecture. Let $2\leq a\leq b$ be even integers. If $G$ is a graph with $n$ vertices such that $\kappa'(G)\geq2$, $n\geq 2a+b+\frac{a^2-3a}{b}-2$, $\delta(G)\geq a$, and