41 problems

Let $G$ be a planar, $4$-edge-connected, $4$-regular simple graph whose size is divisible by $3$. A claw-decomposition is a partition of the edges of $G$ into subgraphs isomorphic…

Jaeger–Swart conjecture. There are no cyclically $7$-edge-connected snarks.

Let an $r$-graph be an $r$-regular graph $G$ such that every odd set $X\subseteq V(G)$ is connected by at least $r$ edges to its complement $V(G)\setminus X$. A graph is $r$-edge-c…

Let $G$ be a graph. A nowhere-zero $\mathbb{Z}_3$-flow on $G$ is a flow with values in $\mathbb{Z}_3$ that is nonzero on every edge; $G$ is 4-edge-connected if deleting fewer than…

A permutation snark is a cycle permutation graph that is not $3$-edge-colourable; a graph is cyclically $5$-edge-connected if removing fewer than five edges cannot separate it into…

Let $G$ be a graph of order $n$ with minimum degree $\delta$ and edge-connectivity $\lambda$. Let $F^{\lambda}_{n,\delta+1}$ be the graph obtained from … by adding $\lambda$ edges…

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…

Let $k$ and $c$ satisfy $0le cle k-1$. For a $(k+c)$-edge-connected graph $G$ with $tau(G)le k-1$, let $pi$ be a partition witnessing the relevant Nash–Williams inequality, and wri…

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.

Let $G$ be a finite connected graph with minimum degree $\delta$ and non-negative Bakry–Émery curvature. A graph is $l$-edge-connected if deleting any set of fewer than $l$ edges l…

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$.

Thomassen's weak linkage conjecture. If $G$ is $k$-edge-connected, then there are $k$ pairwise edge-disjoint paths $P_1,\dots,P_k$ in $G$, with $P_i$ joining $s_i$ and $t_i$ for ea…

Let $r$ be a positive integer, and let $C_{2,r}$ denote the double cycle of length $r$, obtained from a cycle on $r$ vertices by adding a parallel edge to each edge of the cycle. A…

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 a 3-edge-connected pseudo $2$-factor isomorphic cubic bipartite graph, and suppose that $G=G_1*G_2$ is a star-product decomposition. Abreu–Diwan–Jackson–Labbate–Sheehan'…

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 cubic bipartite graph. A graph is pseudo 2-factor isomorphic when the parity of the number of circuits is the same for all its $2$-factors. Let…

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.

Linear edge-connectivity conjecture. There is a positive integer $a$ such that for every tree $T$, there exists a positive integer $l_T$ such that every $a|E(T)|$-edge-connected si…

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…

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 $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…