18 problems

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 $\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.

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

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

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

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…

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 \equiv 1 \pmod {2d}$ be a power of a prime $p$, and let $r$ be the largest integer such that $d \mid \frac{q-1}{p^r-1}$. The subfield…

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

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…

Generalized Reed-type conjecture. Every such graph satisfies