20 problems

A linear forest is a graph whose connected components are paths. The linear arboricity $\operatorname{la}(G)$ of a graph $G$ is the smallest number of linear forests whose union co…

A linear forest is a collection of vertex-disjoint paths. For a graph $G$, its linear arboricity, denoted by $\operatorname{la}(G)$, is the minimum number of linear forests needed…

Planar Linear Arboricity Conjecture. For every planar graph $G$ of maximum degree $\Delta\ge 5$,

Let $G$ be a cubic graph whose number of vertices is divisible by $4$. A linear forest is a forest whose components are paths. Wormald's conjecture. The edges of $G$ can be $2$-edg…

Let $D$ be a $d$-regular digraph, meaning $d^+(v)=d^-(v)=d$ for every vertex $v$, and let $la(D)$ be the minimum number of directed linear forests partitioning its arc set. He–Lin–…

Let $G$ be an undirected graph. A list assignment $L$ assigns a set of colors to each edge, and a linear $L$-coloring chooses a color from each edge's list so that every color clas…

Let $D$ be a finite loopless digraph without parallel arcs, and let $la(D)$ be the minimum number of directed linear forests needed to partition its arc set. Define $\Delta(D)$ as…

Let $G$ be a $d$-regular graph on $n$ vertices. A spanning linear forest is a linear forest containing all vertices of $G$, and its paths are its connected components. Feige–Fuchs…

Let $G$ be a $d$-regular graph on $n$ vertices. A spanning linear forest is a linear forest containing all vertices of $G$, and its paths are its connected components. Magnant–Mart…

Let $D$ be a $d$-regular digraph. A linear diforest is a directed graph whose underlying undirected graph is a vertex-disjoint union of paths; a decomposition into linear diforests…

Linear arboricity conjecture.

Bonamy–Czyżewska–Kowalik–Pilipczuk conjecture. The graph $G$ can be decomposed into $\frac{\Delta-1}{2}$ linear forests and a matching.

Odd-degree planar edge-partition conjecture. The edges of $G$ can be partitioned into $\tfrac{\Delta-1}{2}$ linear forests and one matching.

Directed Linear Arboricity Conjecture. For every directed graph $D$,

Let $G$ be a cubic graph, and let a linear forest be a forest whose components are paths. Bermond–Fouquet–Habib–Pé roche's conjecture. The edges of $G$ can be decomposed into two l…

2-degenerate low-degree conjecture. If $\Delta(G)\in\\{3,4\\}$, then

Let $\Sigma$ be a simple signed graph, let $\Delta(\Sigma)$ be its maximum degree, and let $\chi'_R(\Sigma)$ be the minimum number of colors in a completely reversible zero-free pr…

Strong Ando conjecture. Every cubic graph admits a bisection such that the two induced subgraphs are isomorphic linear forests.

Planar degree-four linear arboricity complexity conjecture. It is NP-complete to determine whether

Planar linear arboricity conjecture. For every planar graph $G$ of maximum degree $\Delta\ge 6$,