129 problems

Triangle-free process independence-number conjecture. The triangle-free process has asymptotically the smallest independence number among all $n$-vertex triangle-free graphs.

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…

Erdős–Gallai–Tuza conjecture. The parameters satisfy

Let $G$ be a triangle-free graph on $n$ vertices, and let $N(G;C_5)$ denote the number of five-cycles in $G$. Erdős's conjecture. A triangle-free graph on $n$ vertices has at most…

For an integer $n\geq 5$, let $C_{5}$ be the cycle of length five, and let the balanced blow-up of $C_{5}$ be the graph obtained by replacing each vertex of $C_{5}$ with an indepen…

Let $G$ be a triangle-free graph on $n$ vertices. The balanced complete bipartite graph conjecture. Among triangle-free graphs on $n$ vertices, the maximum value of the subpath num…

Erdős's conjecture. Deleting at most

Let $G$ be a triangle-free graph on $N$ vertices. Erdős's conjecture. The graph $G$ can be made bipartite by deleting at most … edges; equivalently, $G$ has a cut containing at lea…

A graph is ISK4-free if it contains no induced subdivision of $K_4$, and it is triangle-free if it contains no induced subgraph isomorphic to a triangle. 3-color conjecture for tri…

Andrásfai's conjecture. For all integers $t$ and $n$, the extremal Ramsey–Turán graph is a canonical blow-up of an Andrásfai graph; specifically,

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…

A triangle-free graph is a graph containing no triangle. For an $n$-vertex triangle-free graph, consider subsets of vertices and the edges spanned by each subset. Erdős's sparse ha…

Cambie–Kang conjecture. For every $\varepsilon>0$, there is $d_0\in\mathbb{N}$ such that, if $H$ has maximum degree $d\geqslant d_0$ and

Let $G$ be an $n$-vertex triangle-free graph, and let $m(n;K_3)$ denote the maximum number of cycles in such a graph. The Turán graph $T_2(n)$ is the complete bipartite graph whose…

For $n\in\mathbb{N}$, let … An oriented graph is an orientation of a finite simple graph, and it is triangle-free when its underlying graph contains no triangle. The acyclic number…

Bounded-degree pentagon conjecture, sharp form. For every triangle-free graph $G$,

Erdős's pentagon conjecture. For every triangle-free graph $G$,

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

The outside-NP conjecture. The decision problem $P(\bm{d},r)$ is not in NP, because $\overline{L}$ is coNP-complete and every coNP-complete language is conjectured to lie outside N…

Let $G$ be a triangle-free graph, let $d(G)$ denote its average degree, and let $\alpha(G)$ denote its independence number. The comparison discussed in the source is with the indep…

Let $G$ be a connected triangle-free graph with $n\geq 3$ vertices and $m$ edges. Here, $h(G)$ denotes the maximum number of edges in an uncrossed subgraph of $G$. Triangle-free ti…

Let $G$ be a triangle-free graph on $n$ vertices, and let $D_2(G)$ denote the minimum number of edges that must be removed from $G$ to make it bipartite. Erdős's conjecture. … This…

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…

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

Let $d$ be sufficiently large, and let $G$ be a triangle-free graph. Write $\chi_f(G)$ for its fractional chromatic number, and say that $G$ is $d$-degenerate if every subgraph of…