72 problems

Dallard et al.'s conjecture. Such graphs have bounded tree-independence number; equivalently, they admit tree decompositions whose bags induce subgraphs of bounded independence num…

TxGraffiti's conjecture. One has

Let $G$ be a graph with independence number $\alpha(G)=2$, let $\chi(G)$ denote its chromatic number, and let $K_{\chi(G)}$ be the complete graph on $\chi(G)$ vertices. A weak imme…

Let $G$ be a graph, let $r$ be a positive integer, and let $\alpha(G)$ denote the independence number of $G$. For an $r$-edge-colouring of $G$, let $\operatorname{cp}_r(G)$ be the…

Let $G$ be a graph, let $\alpha(G)$ be its independence number, and let $c(G)$ be the number of cut-vertices of $G$. Graffiti's cut-vertex conjecture. … The paper verifies this ine…

TxGraffiti's conjecture. If $G \not\cong K_4$ and $\Delta(G)\leq 3$, then

Let $G$ be a connected graph with $n(G)\geq 3$. Write $\alpha(G)$ for its independence number, $\Delta(G)$ for its maximum degree, $a(G)$ for its annihilation number, and…

Corona–kernel conjecture. For every graph $G$,

Larson–Pepper's conjecture. The equality $\alpha=a$ holds if and only if $G$ is a König–Egerváry graph and every maximum independent set of $G$ is a maximal annihilating set.

Let $G$ be a finite simple connected graph. For each vertex $v\in V(G)$, let … and let $I_{\mathrm{avg}}(G)$ be the average of these local independence numbers. Let $L_s(G)$ denote…

Let $f(n)$ denote the minimum independence number among $n$-vertex unit-distance graphs in the plane, and let $m_1(\mathbb R^2)$ be the supremum of the upper densities of measurabl…

Let a flag sphere be a flag $(d-1)$-sphere with $n$ vertices, and let $\alpha(\Delta)$ denote the maximum size of an independent set in its graph. Independence-number conjecture. F…

Let $G$ be a bipartite graph with independent sets $C_1$ and $C_2$, with $|C_1|=c_1\leq c_2=|C_2|$, as in Theorem. Let ${\mathcal F}_k(G)$ be the $k$-supertoken graph of $G$, and s…

Let $G$ be a graph, let $\alpha(G)$ denote its independence number, and let $\operatorname{corona}(G)$ and $\operatorname{core}(G)$ denote its corona and core. Let $L_G^c$ be the g…

Turcotte's conjecture. For any positive integer $p$ and any graph $G$ such that $\alpha(G)<p$, we have

Let $G=G_{n,p}$ be the random graph with $n$ vertices and edge-probability $p$, let $calpha(G)$ denote its independence number, and let $\overline{\theta}_1(G)$ denote the minimum…

Let $\Gamma$ be an $n$-vertex $C_4$-free graph, and let $\alpha(\Gamma)$ denote its independence number, the maximum size of a vertex set containing no edges. Erdős's conjecture. T…

Let $\rho$ be a graph parameter, and let $\alpha$-$\rho$ denote its independence variant, obtained by replacing the size constraint in the definition of $\rho$ with a constraint on…

Let $\mathcal{G}$ be a graph class. For graph parameters $\rho$ and $\omega$, say that $\mathcal{G}$ is $(\rho,\omega)$-bounded when bounded clique number in $\mathcal{G}$ implies…

Let $\mathsf{C}_k$ be an odd cycle, and let $L(k,d)$ denote the lower bound for its independence number obtained in Bohman's result. Bohman's conjecture. The lower bound is the exa…

Independence-number-three conjecture. Every graph $G$ with $\alpha(G)\leq 3$ is perfectly divisible.

Independence-number weakening of Hadwiger's conjecture. For any graph $G$,

Independence-number lower-bound conjecture. For any graph $G$,

Kwan–Wigderson's conjecture. For every integer $k$, there exists a graph $G$ with $\alpha(G)=2$ and

Let $G$ be a finite simple graph with independence number $\alpha(G)$ and chromatic number $\chi(G)$. For positive integers $\ell$ with $2\ell\leq\chi(G)$, let…