12 problems

For fixed $r\geq 3$, let $\alpha_r$ be the largest exponent such that every $K_r$-free graph $G$ with $m$ edges satisfies … where $\operatorname{surp}(G)$ is the maximum-cut surplu…

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…

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 bipartition conjecture for K4…

Kr-free correspondence-cover packing conjecture. For every $r\ge3$, there is some $C_r>0$ such that the following holds for

Carlson et al.'s conjecture. Every $K_r$-free $d$-degenerate graph with $m$ edges has surplus

Let $r\geq3$, and let $h(n,k,K_r)$ denote the maximum number of edges that must be deleted from an $n$-vertex $K_r$-free graph to make it $k$-colorable. Clique-free construction co…

For a graph $G$ and positive integers $n,k$, let $h(n,k,K_r)$ be the maximum number of edges that must be deleted from an $n$-vertex $K_r$-free graph to make it $k$-colorable. Shar…

Ajtai–Komlós–Szemerédi conjecture. The factor $\ln\ln\Delta$ can be removed from this bound, so the relevant colouring parameter should have order

Chromatic-number conjecture. The chromatic number of $G$ satisfies

Clique-free ratio conjecture. For every $K_r$-free graph $G$,

For each integer $k\ge 2$, let $d_k=d_k(K_k)$ denote the critical edge density of the complete graph $K_k$. Pfender's recurrence conjecture. The critical edge densities satisfy … T…