9 problems

Let $\mathcal{G}_k$ be the graph class defined in the paper for each $k\in\mathbb{N}$. Hierarchy properness conjecture. For each $k\in\mathbb{N}$, the inclusion … is proper. The co…

Word-representability conjecture. Every 5-regular circulant graph is word-representable.

Let $\text{TGr}_{m,n}$ be the toroidal grid graph formed from the Cartesian product of the cycle graphs $C_m$ and $C_n$, with $m,n\geq 3$, and let $\mathcal{R}(G)$ denote the repre…

Crown-subgraph conjecture. The representation number of $G$ equals either

Let $G$ be a comparability graph, meaning the graph of a partial order. Write $\mathcal{R}_2$ for the class of graphs with representation number at most two, and…

Non-word-representability conjecture. All simplified de Bruijn graphs $S(n,k)$ are non-word-representable for $n\geq 4$ and $k\geq 3$.

Let $G$ be a graph, let $L(G)$ denote its line graph, and let $\Delta(G)$ denote its maximum degree. A graph is word-representable if it admits a word representation, and an orient…

Let $G_n$ be the graph obtained from the crown graph $H_{n,n}$ by adding an apex, that is, a vertex adjacent to every vertex of $H_{n,n}$. The apex crown graph extremal conjecture.…

Let $H_{n,n}$ be the crown graph obtained from the complete bipartite graph on two parts of size $n$ by deleting a perfect matching. The crown graph extremal conjecture. $H_{n,n}$…