63 problems

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

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

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…

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 an $r$-uniform hypergraph with $m$ edges. An $r$-partition of $H$ is a partition of its vertices into $r$ classes; a class meets an edge if it contains at least one vert…

Kuperwasser–Samotij–Wigderson's conjecture. Every $(m,0)$-sparse graph can be partitioned into a $(1,-1)$-sparse graph and an $(m,1-2m)$-sparse graph.

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…

Charikar–Liu–Liu–Vuong conjecture. A $1/\operatorname{poly}(n)$ fraction of the $k$-component forests of the grid graph have balanced component sizes.

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…

Path Partition Conjecture. There exists a partition $V_1,V_2$ of $V(G)$ such that

Judicious partition conjecture. Every weighted graph $G$ of order $n$ admits a $k$-partition $(X_1,X_2,\dots,X_k)$ satisfying both

For a graph $H$, an $H$-freeness witnessing partition of a graph $G$ is a partition certified by obstruction families as described in the source, and it is nontrivial when each obs…

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…

Let $G$ be a graph of positive treewidth $w$. A vertex partition of $G$ is a partition of $V(G)$ into two sets, each of which induces a subgraph of $G$. Linear treewidth partition…

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…

Balikyan–Kamalian conjecture. The problem of deciding whether a subcubic bipartite graph has a locally-balanced $2$-partition with a closed neighborhood remains $NP$-complete.

Let $G$ be a self-complementary graph, meaning that $G$ is isomorphic to its complement. A partition $\mathcal{P}=\{V_{1},V_{2},V_{3},V_{4}\}$ of $V(G)$ is a rectangle partition if…

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 a graph be partitioned into two parts, and call a vertex friendly when it satisfies the friendliness condition for its part (the source does not specify the condition in this s…

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…