27 problems

Let $G$ be a connected graph of order $n$, and let $\omega(G)$ denote its clique number. Clique-number refinement. If … then … This conjecture is motivated by the expectation that…

Let $q>3$ be a prime power, and consider a Peisert graph of order $q^4$ containing the subfield $\mathbb{F}_q$ as a clique. Yip's Peisert graph conjecture. The subfield…

Let $G$ be a graph with $n$ vertices, let $lambda1,dots,lambdan$ be the eigenvalues of its adjacency matrix, and let $s^+$ be the sum of the squares of its positive eigenvalues:…

Let $\mathcal{G}$ be a hereditary graph class. A graph is $2$-degenerate if every induced subgraph has a vertex of degree at most $2$, and $\mathcal{G}$ is…

Ghalavand et al.'s conjecture.

Approximation conjecture. There is a function $f$ such that for every integer $k$, there is a polynomial-time algorithm which, given a tournament $T$, correctly concludes that…

Let $\mathcal{G}$ be a hereditary graph class. A graph $H$ is $H$-free in $\mathcal{G}$ when graphs in the relevant subclass have no induced subgraph isomorphic to $H$. The class…

Let $G$ be a graph of order $n(G)$, local metric dimension $\dim_l(G)$, and clique number $\omega(G)$. The hypothesis $n(G)\geq\omega(G)+1\geq 4$ is equivalent to considering graph…

A hereditary weakly sparse class is a graph class closed under induced subgraphs and excluding some biclique $K_{t,t}$ as a subgraph. Hajebi's conjecture. Every hereditary weakly s…

Ghalavand's conjecture. The local metric dimension of $G$ satisfies

Elphick–Linz–Wocjan conjecture. For every graph $G$,

A tournament $T$ is $k$-clique-critical if $\operatorname{\overrightarrow{\omega}}(T)=k$ and $\operatorname{\overrightarrow{\omega}}(T-v)=k-1$ for every $v\in V(T)$. The infinite c…

For a tournament $T$, let $N^+(v)$ denote the out-neighbourhood of $v$, and let $\operatorname{\overrightarrow{\omega}}(T)$ denote the clique number. The local-to-global clique-num…

For a tournament $T$, let $\operatorname{dom}(T)$ be its domination number and let $\operatorname{\overrightarrow{\omega}}(T)$ be its clique number. The domination-to-clique cluste…

Let $d>1$ be an integer, let $q$ be a prime power with $q^n\equiv 1\pmod {2d}$, and suppose that $\mathbb{F}_q$ is a maximal subfield clique in $GP(q^n,d)$. Theorem 1.7 establishes…

Let $V$ be a $2$-dimensional $F_p$-subspace of $\mathbb{F}_{p^4}$ containing $1$, and let $g$ be the primitive element used to define the graph $PP(p^4,p+1,I)$. Two-dimensional cli…

For a prime $p\geq 3$, consider subsets $I\subset\{0,1,\ldots,p\}$ with $0\in I$ and $|I|=(p+1)/2$, and the associated graph $PP(p^4,p+1,I)$. Let $g$ be the primitive element used…

Let $X=PP(q,2d,I)$ be a semi-primitive pseudo-Paley graph with $q=p^{2rt}$, where $r$ is even, and assume … A maximum clique is a clique of size $\omega(X)$. Two-clique conjecture.…

Let $X=PP(q,2d,I)$ be a semi-primitive pseudo-Paley graph with $q=p^{2rt}$, where $r$ is even. A maximum clique is a clique of size $\omega(X)$. Canonical-subspace conjecture. If ……

Relative-moment conjecture. A similar statement should hold in general, or at least for a wide class of weights $W$ and scalings $\lambda_n$.

Let $G_{n,r_n}$ be the split-and-drift random graph, let $_n$ denote its parameter, and let $\kappa_n$ be its clique number. In the intermediate regime, $r_n \to +\infty$ and…

Let $\Gamma$ be a connected, non-complete edge-regular graph, and let $\overline{\Gamma}$ be its complement. Consider the clique adjacency bound for the clique number…

Let $\Gamma$ be a strongly regular graph with parameters $(v,k,\lambda,\mu)$, clique adjacency bound less than $-k/s$, and least eigenvalue $s$. Clique adjacency bound conjecture.…

Let $G$ be a graph with $n$ vertices and $m$ edges. Let $\phi$ denote the graph parameter used in the source, and let $\epsilon$ denote the irregularity measure defined earlier in…

Let $G$ be a non-complete undirected graph with adjacency eigenvalues $\mu_1\geq\mu_2\geq\cdots\geq\mu_n$, $m=|E|$ edges, and clique number $\omega$. Bollobás–Nikiforov's conjectur…