68 problems

Extremal edge-count conjecture. For any odd $n\geq 5$,

For $n\geq5$, consider the balanced blow-up of the $5$-cycle $C_5$, obtained by replacing each vertex of $C_5$ by an independent set of size $\lfloor n/5\rfloor$ or…

Let $G$ be a triangle-free graph on $n$ vertices. Erdős's conjecture. The graph $G$ contains at most $(n/5)^5$ cycles of length $5$. The balanced blow-up of the $5$-cycle $C_5$ att…

Let $G=(V,E)$ be a triangle-free graph of average degree $d$, let $Z_G(\lambda)$ denote its independence polynomial, and let $W$ be the Lambert $W$-function, defined by…

Let $G=(V,E)$ be a triangle-free graph of average degree $d$, let $Z_G(\lambda)$ denote its independence polynomial, and write $Z_G'(1)$ for its derivative at $1$. Occupancy-fracti…

Triangle-free recolouring conjecture. Any triangle-free graph $G$ is $k$-recolourable for all

Let $G$ be a graph, and let $d$ be a nonnegative integer such that $G$ is $d$-degenerate, meaning that every subgraph of $G$ has a vertex of degree at most $d$. Let $\triangle$-fre…

Davies–Jenssen–Perkins–Roberts conjecture. As $d\to\infty$,

Let $G$ be a triangle-free graph, let $\chi(G)$ denote its chromatic number, and let $\rho(G)$ denote its spectral radius. Spectral-radius chromatic bound. Every triangle-free grap…

Let $n$ tend to infinity, and let $G$ be a triangle-free graph on $n$ vertices. Write $\chi_f(G)$ for its fractional chromatic number. Cames van Batenburg–de Joannis de Verclos–Kan…

Let $G$ be a triangle-free graph, and let $d_G(v)$ denote the degree of a vertex $v\in V(G)$. Consider a probability distribution on the independent sets of $G$. Kelly–Postle's loc…

Let $G$ be a triangle-free graph satisfying $CD(0,\infty)$ with both the unweighted normalized and non-normalized Laplacians. An induced $k$-cycle conjecture. $G$ contains no induc…

Finite forbidden-subgraph conjecture for $\mathfrak{D}_4$. There exists a finite family $\mathscr{F}$ of graphs such that $\mathfrak{D}_4$ is the class of maximal triangle-free gra…

For each positive integer $n$, let $\vec t(n)$ be the maximum dichromatic number of an oriented triangle-free graph of order $n$. Maximum dichromatic number conjecture. … This conj…

For each positive integer $n$, let $\vec a(n)$ be the minimum of $\vec\alpha(D)$ over all oriented triangle-free graphs $D$ of order $n$, where $\vec\alpha(D)$ denotes the maximum…

Critical maximum-cut conjecture. There exists $c^*>0$ and a continuous function $\delta:(c^*,\infty)\to(0,1/2]$ such that:

The $=5$ case of Vizing's conjecture. Every $5$-regular triangle-free graph has chromatic number at most $4$.

Ahanjideh–Ekim–Yıldız conjecture. For all natural numbers $d\geq 2$ and $m$, we have

Let $G$ be a connected, twin-free and triangle-free graph of order $n$. Write $i_{\text{max}}(G)$ for the number of maximal independent sets of $G$. Minimum maximal-independent-set…

$Z(d)$ conjecture. For odd $d\geq 21$,

General formula in terms of $Z(d)$.

Intermediate-value conjecture. For $7\leq d<i<Z(d)$,

Intermediate fractional colorability conjecture. Every such graph $G$ is fractionally $19/7$-colorable.

Heckman–Thomas planar conjecture. Every subcubic triangle-free planar graph is fractionally $8/3$-colorable.

Let $G$ be a regular triangle-free graph on $n$ vertices. Let $\lambda_n(G)\leq\cdots\leq\lambda_1(G)$ be the eigenvalues of the adjacency matrix of $G$. Brandt's conjecture. … The…