15 problems

A word-representable graph $G$ is a graph represented by a word over its vertices in which two vertices alternate if and only if they are adjacent. Its representation number…

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…

A word-representable graph $G$ is a graph represented by a word over its vertices in which two vertices alternate if and only if they are adjacent. Its representation number…

Let a path of double-arborescences have $n$ vertices and clique number $k$. Minimum-word-representant length conjecture. The length of a minimum-word-representant of the path is al…

Non-word-representability conjecture. For every odd integer $n\ge 3$, the graph $\mu(C_n)$ is not word-representable.

Let $S(n,k)$ denote the simplified de Bruijn graph with positive integer parameters $n$ and $k$. Petyuk's conjecture. $S(n,k)$ is non-word-representable for $n\geq 4$ and $k\geq 3$…

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

A graph $G$ is $d$-Tverberg if it is induced as the nerve of a partition of some sufficiently large set of points in $\mathbb{R}^d$. Consider the bipartite graph shown in Figure; u…

Bipartite representation-number conjecture. Every bipartite graph on $n$ vertices has representation number at most $n/4$.

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