170 problems

Let $H$ be a bipartite graph and let $G$ be a graph. Write $v(H)$ and $e(H)$ for the numbers of vertices and edges of $H$, and likewise $v(G)$ and $e(G)$ for $G$. Let $\hom(H,G)$ d…

Erdős–Simonovits' conjecture. If $e_F\geq e_{F'}$, then, for every graph $G$,

Let $\mathcal{M}$ be a graph class that is proper, minor-closed, and union-closed. For graphs $G$ and $H$, write $G =_{\mathcal{M}} H$ when $\hom(K,G)=\hom(K,H)$ for every…

Benjamini–Häggström–Mossel range conjecture. If $f\in_r{\operatorname{Hom}}_{v_0}(Q_n)$, then

A graph $X$ is core-complete if $X$ is isomorphic to its core $X^{\bullet}$ or its core is a complete graph. Strongly regular graphs are graphs with constant parameters governing t…

Core conjecture. For any positive integer $k$, the graph $QI(k^2,k)$ is a core.

Kahn's sharp range conjecture. The absolute constant in the bound $R(f)=O(1)$ with high probability can be taken to be $5$; equivalently,

Brakensiek–Guruswami conjecture. For every $k\geq 1$ and $n\geq 3$, the problem

Jaeger–Zhang conjecture. Every planar graph of odd-girth at least $4k+1$ admits a homomorphism to

Circular-colouring density conjecture. If $G$ has no $(p,q)$-colouring, then there exist positive rational numbers $\varepsilon_{p,q}$ and $c_{p,q}$, depending on $p$ and $q$, such…

Let $n,k,k'$ be integers, and write $k'=qk-r$ with $0\leq r<k$. Let $\operatorname{KG}(n,k)$ denote the Kneser graph on the $k$-subsets of $[n]$. Stahl's Kneser graph homomorphism…

Parity graph homomorphism dichotomy conjecture. Every parity graph homomorphism problem is either solvable in polynomial time or $\oplus\mathrm{P}$-complete; moreover, the polynomi…

Optimal covering-array conjecture. A $CA(n,QI(n,k),k)$ is an optimal covering array; equivalently, for positive integers $n,k$ with $n\geq k^2$, …

Let $G_n$ be a family of bipartite graphs with $|G_n|\to\infty$, each having maximal degree $d$, where $d$ is independent of $n$. For vertices $v_n\in G_n$, let $f_n$ be uniformly…

Homomorphism cancellation conjecture. If, for all graphs $G,H\in\mathcal{G}$,

Nešetřil's universal target conjecture. For every integer $k$, there is a graph $H$ of girth at least $k$ and an integer $N$ such that every cubic graph $G$ of girth at least $N$ h…

Nešetřil's Pentagon Conjecture. If $G$ is a cubic graph of sufficiently high girth, then $G$ is homomorphic to $C_5$.

Triangle-free cubic graph conjecture. Every triangle-free cubic graph is homomorphic to $PQ_4$.

Seymour's conjecture. Every planar graph whose odd cycles all have length at least $2k+1$ has a homomorphism to $PQ_{2k}$.

Let $H$ be a graph that is $k$-colorable. For a finite graph $G$, let ${\rm Hom}(G,H)$ denote the space of graph homomorphisms from $G$ to $H$, with adjacency given by changing one…

Let $A$ be a set, let $\theta\neq 0$ be a limit cardinal number, and let $\operatorname{Card}$ denote the class of cardinal numbers. A binary relation on $A$ is a subset…

Let $A$ be a set, let $\theta\neq 0$ be a limit cardinal number, and let $\operatorname{Card}$ denote the class of cardinal numbers. A binary relation on $A$ is a subset…

Let $A$ be a set, let $\theta$ be an infinite cardinal number, and write $2^{2^{\theta}}$ for the cardinal obtained by iterating the power-set operation twice. A binary relation on…

Let $H$ be a graph, and let $G$ be a graph of order $n$ with average degree $\overline d(G)$. Write $v(H)$ and $e(H)$ for the numbers of vertices and edges of $H$, and let…

Let $H$ be a graph, and let $G$ be a graph of order $n$. Write $v(H)$ and $e(H)$ for the numbers of vertices and edges of $H$, $\hom(H,G)$ for the number of homomorphisms from $H$…