25 problems

Let $k$ and $c$ be integers with $0\le c\le k-1$. For $0\le c\le k-2$, let $\mathcal{H}_1(n,k,c)$ be the class of all $(k+c)$-edge-connected graphs $H$ of order $n$ for which there…

Lau's Extension Theorem. There are $k$ edge-disjoint $S$-subgraphs that extend $v$ and balance $S\cup R$ if either $v\in S$, $d(v)=Qk$, and $P_k(v)$ is a balanced edge subpartition…

Rich-flow conjecture for 3-edge-connected graphs. Every $3$-edge-connected graph with maximum degree $\Delta$ admits a rich $(\Delta+3)$-flow.

Cyclic 4-edge-connectivity conjecture. Up to isomorphism, the Petersen graph is the only cyclically $4$-edge-connected cubic graph with cycle covering ratio $7/5$.

Let $G$ be a cyclically $5$-edge-connected odd $2$-factored snark, where a snark is a bridgeless cubic graph of chromatic index four and odd 2-factored means that every cycle in ev…

Let $G$ be an essentially $4$-edge-connected pseudo $2$-factor isomorphic cubic bipartite graph, where essentially $4$-edge-connected means 3-edge-connected with no non-trivial 3-e…

Let $G$ be a 3-edge-connected 2-factor isomorphic cubic bipartite graph. Abreu–Diwan–Jackson–Labbate–Sheehan's conjecture. Then $G$ is a 2-factor Hamiltonian cubic bipartite graph.…

Let $G$ be a $k$-edge-connected graph, where $k\ge 2$, and let $H\subset G$ be a minimum-edge spanning $k$-edge-connected subgraph, meaning a spanning $k$-edge-connected subgraph w…

Priestley's conjecture. $k$-ECSM admits a polynomial-time $(1+O(1/k))$-approximation algorithm.

For $0\leq t\leq r$, let $m(t,r)$ be the maximum integer $s$ such that every $t$-edge-connected $r$-graph has $s$ pairwise disjoint perfect matchings. The upper-bound conjecture. F…

Let $\mathcal{A}_{n}^{\kappa',\delta}$ be the set of graphs of order $n$ with minimum degree $\delta$ and edge connectivity $\kappa'$. Let $B_{n,\delta+1}^{\kappa'}$ be the graph o…

Polynomial edge-connectivity conjecture. There are two positive integers $a$ and $n$ such that every $a|E(T)|^n$-edge-connected simple graph whose size is divisible by $|E(T)|$ adm…

Barát–Thomassen conjecture. For every tree $T$, there exists a positive integer $k_T$ such that every $k_T$-edge-connected simple graph whose size is divisible by $|E(T)|$ admits a…

Let $G$ be a $k$-edge-connected graph, meaning every edge cut of $G$ has size at least $k$, with $k\geq 4$. A spanning closed trail is a closed trail containing every vertex of $G$…

Let $m\geq 1$ be an integer, and let $G$ be a $d$-regular graph with $d\geq 2m+2$. Let $\lambda_2(G)$ be the second-largest adjacency eigenvalue of $G$, and let $\sigma(G)$ denote…

Let $G$ be a $3$-edge-connected graph. A matching is a set of pairwise vertex-disjoint edges, and a 3-edge-cut is an edge cut of size three. A matching is deletable when all its ed…

Let $G$ be a $3$-edge-connected graph. Its Frank number $f(G)$ is the minimum number of orientations needed so that every edge is deletable in at least one of them. Frank-number co…

Rainbow disconnection bound. The conjecture states

Minimum-degree-three conjecture. Every 2-edge-connected graph of minimum degree at least three has the strong parity property.

Let $k\geq 3$, and let $G$ be an edge-optimal minimally $k$-edge-connected graph of order $n$, meaning a minimally $k$-edge-connected graph with largest average edge-connectivity a…

Let $G$ be a $4$-edge-connected graph with maximum degree at most $5$. The bounded-degree decomposition conjecture. The graph $G$ can be decomposed into two connected factors $G_1$…

Let $G$ be a graph, let $k$ be an integer with $k\ge 3$, and let $p:V(G)\rightarrow Z_k$ satisfy … A $p$-orientation is an orientation satisfying the prescribed modulo-$k$ out-degr…

Let $T$ be a fixed tree with maximum degree $\Delta_T$, and let $|E(T)|$ denote its number of edges. A graph is $T$-decomposable if its edges can be partitioned into sets each indu…

O's conjecture. For $t\geq 3$, if

Let $f(A,B)$ be the partitioning-function quantity discussed in the paper, with $A$ and $B$ positive integers. The asymptotic conjecture for $f(A,1)$. … The source notes that only…