14 problems

Normalized algebraic-connectivity conjecture.

Cheeger-constant Nordhaus-Gaddum conjecture. If $G\neq S_n$, then

Weak Graph Complement Conjectures. There exist universal constants $b,b_+,b_\nu<2$ such that, for every graph $G$,

Graph Complement Conjecture for $\nu$. For any graph $G$,

Positive semidefinite Graph Complement Conjecture. For any graph $G$,

Graph Complement Conjecture. For any graph $G$,

Jamison and Sprague's conjecture. For every integer $k\ge 1$, there is a graph $G$ with

Algebraic lower-bound conjecture. The pair $(x,y)$ satisfies

De Caen–Erdős–Pullman–Wormald conjecture.

Let $G$ be a simple graph of order $n\ge 2$, with Laplacian eigenvalues … The Laplacian spread conjecture. The inequality … holds, or equivalently … Moreover, equality holds if and…

Let $G$ be a finite simple graph and let $\overline{G}$ denote its complement. Let $\mu(G)$ denote the Colin de Verdière parameter. Colin de Verdière's graph complement conjecture.…

Self-complementary Erdős–Hajnal conjecture. For every graph $H$, there exists a constant $\epsilon(H)>0$ such that every $\{H,H^c\}$-free graph $G$ has either a clique or a stable…

Let $G$ be a graph, let $\overline{G}$ denote its complement, and for $k\geq 3$ let $f_k(G)$ be the number of frustrated $k$-cycles, where a cyclic ordering $v_1v_2\dots v_k$ is fr…

Xu–Liu conjecture. Then $G$ and $\overline{G}$ have the same degree sequence. This conjecture concerns graphs whose chromatic polynomial agrees with that of their complement. The p…