49 problems

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…

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

TxGraffiti's conjecture. One has

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 $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…

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

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

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…

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…

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…

Weak Hadwiger conjecture. Every graph $G$ with $\alpha(G)\leq 2$ contains

Weighted Caro–Wei obstruction conjecture. Unless $G$ contains either a clique $K\subseteq V(G)$ such that

Let $G$ be a connected cubic, equivalently 3-regular, graph. Let $\alpha(G)$ denote the independence number of $G$, and let $\mu(G)$ denote its matching number. Caro–Davila–Pepper…

Let $G$ be a connected $r$-regular graph with $r>0$. Let $\alpha(G)$ denote the independence number of $G$, and let $\mu(G)$ denote its matching number. TxGraffiti's independence–m…

Botler et al.'s conjecture. Let $G$ be an $n$-vertex graph with $\alpha(G)\leq2$. For any positive integer $\ell$ with $\ell<\lceil n/2\rceil$, we have

Plummer–Stiebitz–Toft conjecture. Every $n$-vertex graph $G$ with $\alpha(G)\leq2$ contains $K_{\lceil n/2\rceil}$ as a minor.

Babai's conjecture. For every $\varepsilon>0$, there exists a minimal Cayley graph $G=(V,E)$ such that

Let $G$ be a graph, let $\alpha(G)$ be its independence number, let $v$ be the number of vertices of $G$, and let $\Delta$ be its maximum degree. AGX's order-to-degree conjecture.…

Let $G$ be a graph, let $\alpha(G)$ be its independence number, let $v$ be the number of vertices of $G$, and let $\Delta$ be its maximum degree. AGX's square-root conjecture. … Th…

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…

Let $G$ be a graph, let $\alpha(G)$ be its independence number, and let $r(G)$ be its graph radius. Graffiti's radius conjecture. … The source verifies the intended bound for the l…

Let $G$ be a graph, let $\alpha(G)$ be its independence number, and let $\bar d$ be the average distance between distinct vertices of $G$. Graffiti's average-distance conjecture. ……

$\mathbf{W_2}$ characterization conjecture. For every graph $G$, the following assertions are equivalent: