14 problems

Let $G$ be a graph. The triangle packing number $\nu(G)$ is the maximum number of edge-disjoint triangles in $G$, and the triangle cover number $\tau(G)$ is the minimum number of e…

Yuster's conjecture. For every fixed $\varepsilon>0$, if

Let $G=(V,E)$ be a graph, let $w\colon E\to\mathbb{Z}_+$ be an integer-valued edge-weight function, and let $\nu_w(G)$ and $\tau_w(G)$ denote, respectively, the maximum total weigh…

Near-perfect packing conjecture. If

Győri–Keszegh's conjecture. For every such graph $G$ and every greedy partition $P$,

Rainbow triangle-packing conjecture. The graph $K_n$ contains a rainbow subgraph that is a disjoint union of triangles covering all but at most $C$ vertices, for some absolute cons…

The 3/2 random-graph conjecture. For all $C>3/2$ and $G=G(n,m)$, with high probability,

Let $G$ be an arbitrary graph on $n$ vertices, and let $\overline{G}$ denote its complement. Jacobson's conjecture. One of $G$ and $\overline{G}$ has a triangle packing with at lea…

Let $G$ be a graph on $n$ vertices, let $\overline{G}$ denote its complement, and define … where $\nu^*(G)$ is the fractional triangle-packing number of $G$. Near-bipartite stabili…

Let a graph be co-triangle-free if its complement is triangle-free, and let $g(n)$ be the largest number $m$ such that every co-triangle-free graph on $n$ vertices contains a trian…

Let $G$ be a $K_4$-free graph on $n$ vertices with $t_2(n)+m$ edges, where $t_2(n)=\lfloor n^2/4\rfloor$ is the number of edges in the $2$-partite Turán graph on $n$ vertices. Edge…

Let $G$ be a graph, and let $(V_1,V_2,V_3)$ be a triple of pairwise disjoint vertex sets such that each pair $(V_i,V_j)$ is $(\varepsilon,p)$-regular, meaning that for all…

Let $G$ be a graph with $n$ vertices and $m$ edges. Call $G$ $(1-\delta)$-hard to make triangle-free if … where $\tau_t(G)$ is the minimum number of edges meeting every triangle, a…

Let $G$ be a graph with $n$ vertices and $m$ edges. Call $G$ $(1-\delta)$-hard to make triangle-free if … where $\tau_t(G)$ is the minimum number of edges meeting every triangle of…