34 problems

Lee, Loh and Sudakov's conjecture. Every digraph $D$ with minimum outdegree at least $d+1$ admits a bipartition $V(D)=V_1\cup V_2$ such that

Alon's inversion-number partition conjecture. For every two positive integers $k_1,k_2$, there exists an integer $f(k_1,k_2)$ such that every oriented graph $D$ with

Let $d$-regular graphs be graphs in which every vertex has degree $d$, and call a partition of the vertex set into two parts an internal partition when every vertex has at least as…

Erdős–Lovász–Tihany Conjecture. If

Ban–Linial conjecture. Every cubic graph has an external split $(X,Y)$ satisfying

Let $G$ be a graph and let ${\cal P}$ be a monotone partition of $V(G)$ into cliques. Assume that the box graph $b(G;{\cal P})$ is a chordless cycle. The logarithmic cyclic-box con…

Let $G$ be a graph, and let ${\cal P}=(A_1,\ldots,A_k)$ be a monotone partition of $V(G)$ into cliques. The box graph $b(G;{\cal P})$ has a chordless cycle…

Let $G$ be a finite simple triangle-free planar graph. A partition of $G$ into an independent set and a forest means that there is a partition $(V_1,V_2)$ of $V(G)$ such that…

Polynomial graph-partition conjecture. If $\mathcal{H}$ has bounded VC$_2$ dimension, then it has an $\varepsilon$-graph partition with $M=\operatorname{poly}(1/\varepsilon)$ many…

For a graph $G$, let ${\rm iso}(G,k)$ be the maximum number of pairwise disjoint $k$-clique isolating sets in a partition of $V(G)$, and let ${\rm iso}_c(G)$ be the analogous numbe…

Let $k \geq 3$ be an integer. A $k$-clique isolating set of a graph is a vertex set whose closed neighborhood leaves no copy of $K_k$. The partition conjecture. Every connected gra…

Let $G$ be a graph of order $n$, and let $k$ be an integer at least $2$. A partition $\mathcal{P}$ of $V(G)$ is $k$-proper if every part $P\in\mathcal{P}$ induces a $k$-connected s…

Linear-connectivity partition conjecture. There exists a constant $c>0$ such that the vertices of every strongly $c\cdot ktl$-connected digraph $D$ with $\delta(D)\geq n-l$ can be…

Let $D$ be a digraph without infinite directed paths. Infinite Gallai–Milgram conjecture. There is a vertex-partition $d4ab$ of $D$ into directed paths and an independent set $U$ o…

Let $d_0,d_1,\ldots,d_k\geq1$ satisfy … and let $R(n;d_0,\ldots,d_k)$ be the number of partitions of the edges of $K_n$ into spanning regular subgraphs of degrees $d_0,\ldots,d_k$.…

Let $H$ be a bipartite graph that is not a forest. Write $f(r,H)$ for the least integer $k$ such that every $H$-free $(r,k)$-graph does not exist, and write…

Let $G$ be a 2-connected graph of order $n$, and let $n=n_1+n_2+\cdots+n_k$ be a partition of $n$. A subset $A\subseteq V(G)$ is nearly connected if it is contained in a subtree…

For $\varepsilon>0$, a graph $G$ is $(N,\varepsilon)$-restricted if its vertex set can be partitioned into at most $N$ subsets that are $\varepsilon$-restricted in $G$, where a sub…

Let $n$ be divisible by $3$ and let $G$ be a $K_4$-free graph on $n$ vertices. A balanced $3$-partition divides $V(G)$ into three classes of size $n/3$; class-edges are edges whose…

Let $n$ be even and let $G$ be a $K_4$-free graph on $n$ vertices. A balanced $2$-partition is a partition $V(G)=A\cup B$ with $|A|=|B|=n/2$. Balanced max-part conjecture for K4-fr…

For a graph $G$, let $D_2(G)$ be the minimum number of edges that must be deleted to make $G$ bipartite. Fix $r\geq3$, and let $G$ be an $n$-vertex $K_{r+1}$-free graph. Sudakov's…

Forest-path partition conjecture. Every planar graph without $4$-cycles and $6$-cycles has an $(\mathcal{F}_1,\mathcal{F})$-partition.

Maximum-average-degree partition conjecture. If

Odd-order obstruction conjecture. No $\sigma_n$-$k$-partition with $k>1$ and $n$ odd has a transitive $\sigma_n$-orientation.

Odd-order obstruction conjecture. No $\sigma_n$-partition with $n$ odd has a transitive $\sigma_n$-orientation.