94 problems

Let $G$ be a graph, let $d_v\coloneqq\deg_G(v)$, and let $H$ be an edge-weighted graph, possibly with loops. Define the weighted homomorphism count by … where $H(a,b)$ is the edge…

Feder–Vardi dichotomy conjecture. For any relational structure $T$, $\textsc{Csp}(T)$ is either NP-complete or polynomial-time solvable.

Let $H$ be a $d$-regular graph, and let $G$ be a graph possibly with loops. Regard $G$ as its symmetric adjacency matrix, and suppose that it has at most one positive eigenvalue. S…

Let $G$ be a bipartite graph, let $d_u$ denote the degree of $u\in V(G)$, and let $H$ be a loop-graph. Write $\hom(G,H)$ for the number of graph homomorphisms from $G$ to $H$. Galv…

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…

Let $(G,\sigma)$ be a signed planar graph, and let $g_{ij}(G,\sigma)$ denote the corresponding signed girth parameter; let $SPC(k)$ be the signed projective cube of dimension $k$,…

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…

Circular homomorphism conjecture. Every planar graph $G$ of girth at least $4k$ admits a homomorphism to $C_{2k+1}$. Equivalently,

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

Let $G_n$ be a family of vertex-transitive bipartite graphs with $|G_n|\to\infty$. Let $\Delta_n$ denote the diameter of $G_n$, and let $f_n$ be uniformly random in…

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

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

Lovász's conjecture. The equation is true for $T=C_{2r+1}$, $r\geq 1$, and all $n$.

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

Let $\mathcal{M}_1$ and $\mathcal{M}_2$ be two distinct immersion-closed and union-closed graph classes. For graphs $G$ and $H$, write $G =_{\mathcal{M}} H$ when…

For a graph $G$, its Hadwiger number is the largest integer $t$ such that $G$ contains the complete graph $K_t$ as a minor. Two graphs are homomorphism indistinguishable over a gra…

Reduced TAS-tree conjecture. For every undirected tree that is not a caterpillar, has at least $2$ vertices of even degree, and has no isomorphic pair, there exists some orientatio…

TAS-tree conjecture. For every undirected tree, there exists some orientation that has the tournament anti-Sidorenko property.

Let $G$ be an antiferromagnetic graph, and let $H$ be any graph. Universal bipartite-swapping conjecture. Then … Here $H\times K_2$ is the categorical product with the two-vertex c…

Let $H$ be a graph and let $q\geq 2$. Write $K_q$ for the complete graph on $q$ vertices, and let $H\times K_2$ denote the categorical product with the two-vertex complete graph. Z…

Let $X$ be an antipodal, non-bipartite distance-regular graph of diameter $3$. An endomorphism of $X$ is a graph homomorphism from $X$ to itself, and a subgraph has diameter $2$ wh…