21 problems

Bollobás–Scott's conjecture. Every graph $G$ has a bisection in which every vertex $v$ has at least

Let $G$ be a planar graph. A graph is $k$-degenerate if every subgraph $H$ of it has minimum degree $\delta(H)\leq k$, and $G$ is $(m,n)$-partitionable if its vertex set can be par…

Let ${\cal P}$ and ${\cal Q}$ be additive hereditary graph properties. A graph belongs to ${\cal P}\circ{\cal Q}$ if its vertex set can be partitioned into two parts inducing graph…

Highly connected instance conjecture. Highly connected instances are more likely to contain highly connected partitions.

For a graph on $n$ vertices, a bisection is a red-blue colouring in which the colour-class sizes are equal, or differ by one when $n$ is odd. An external bisection has at least hal…

Let $d\text{?}$ be a natural number, and let a nontrivial internal partition of a graph be a partition into two nonempty parts in which every vertex has at least half of its neighb…

Optimality conjecture. The results obtained for general $K^*$, despite being seemingly unsatisfactory, are conjectured to be optimal.

Lee–Loh–Sudakov conjecture. Every digraph $D$ with $m$ arcs and minimum outdegree at least $d$ admits a bipartition $V(D)=V_1\cup V_2$ with

Borodin–Ivanova conjecture. Every planar graph with girth at least $6$ admits a $({\cal P}_{3},{\cal P}_{3})$-partition.

Let $\mathcal{H}$ be an $r$-uniform hypergraph with $m$ edges, and partition its vertex set into $k$ parts. The quantity to maximize is the minimum, over the $k$ parts, of the numb…

Let $D$ be a digraph with $m$ arcs and minimum outdegree at least an integer $d\geq 2$. For a bipartition $V(D)=V_1\cup V_2$, write $e(V_i,V_j)$ for the number of arcs directed fro…

Let $G$ be a connected graph with maximum degree $k \geq 3$, distinct from $K_{k+1}$. For integers $s \geq 2$ and $p_1,\ldots,p_s \geq 0$ satisfying … a $(p_1,\ldots,p_s)$-partitio…

Let $G=(V,E)$ be the graph and let $k,k'$ be the partition parameters, with $r$, $r'$, and $R$ as defined for the corresponding clique inequalities. For a clique $C$, write $y(C)$…

The paper considers the graph classes appearing in Theorem 1 and the property of being partitionable, meaning that the vertex set can be partitioned into a triangle-free induced su…

Partition conjecture. If

Let $G$ be a graph with maximum degree $\Delta$. An equitable partition is a partition of the vertex set into parts whose sizes differ by at most one, and an induced forest is a ve…

Miclo's conjecture. It should be possible to find a family $\{\psi_i\}$ of $k$ pairwise disjointly supported functions $\psi_i:V\to\ell_2$ such that each $\mathcal R_G(\psi_i)$ is…

Louis–Raghavendra–Tetali–Vempala conjecture. The bound

Higher-order spectral partitioning conjecture. There are $k$ eigenvalues close to zero if and only if the vertex set $V$ can be partitioned into $k$ subsets, each defining a sparse…

Let $G$ be a random regular graph with $N$ vertices and $|E|$ edges, and partition its vertices into two equal-sized subgraphs. Let $C_{\rm min}$ and $C_{\rm max}$ denote, respecti…

Let $G$ be a random $r$-regular graph with $N$ vertices, edge set $E$, maximum cut size $|MC|$, and minimum bisection size (bisection width) $|BW|$. Here $|E|$ is the total number…