9 problems

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…

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

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

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…

Let $G$ be a planar graph. An equitable partition of $G$ is a partition of its vertex set into parts whose sizes differ by at most one, and an induced forest is a vertex-induced su…