19 problems

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

Graph Complement Conjecture. For any graph $G$,

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

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

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

Elphick–Aouchiche conjecture. For every graph $G$ on $n$ vertices,

Normalized algebraic-connectivity conjecture.

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

Let $G$ be a graph of order $n\geq 3$, let $\overline{G}$ denote its complement, and let $S_{a,b}$ denote the graph referenced in the source as the relevant exceptional complement.…

Let $G$ be a graph on $n\geq 3$ vertices, let $\overline{G}$ denote its complement, and let $e(\overline{G})$ be the number of edges in the complement. The parameter $q(G)$ is the…

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

Let $f$ be a function on the nonnegative integers, and call it a $χ$-binding function for an ideal $\mathcal I$ when $χ(G)\le f(ω(G))$ for every $G\in\mathcal I$. Say that $f$ has…

Let $G$ be a finite simple graph with connected complement, and let $\sigma(G)$ denote the number of Laplacian eigenvalues of $G$ at least its average degree. For integers…

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…

For a graph $F$, let $\Delta(F)$ denote its maximum degree, let $\overline{F}$ denote its complement, and let $\operatorname{cp}(G)$ be the minimum number of cliques in a partition…

A clique partition of a graph $G$ is a collection of complete subgraphs that partitions the edge set of $G$, and let $\operatorname{cp}(G)$ be the smallest number of cliques in suc…