2 problems

For each $d\geq3$, let $p^*(d)$ be the minimum value of $p\in\{1,2,\ldots,\lfloor d/2\rfloor\}$ such that a.a.s. the random graph $\mathcal{G}_{n,d}$ has a $p$-orientation. Define…

Let $G$ be a cubic graph that admits a perfect matching. A $4$-weak bisection is a bisection of $G$ in which every monochromatic component has at most $4$ vertices. Revised Ban–Lin…