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…

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

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…

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

Dismantling characterization. $\operatorname{Recol}_{\mathbb{M}}(N)$ is trivial if and only if $N$ dismantles to the loop $M^\ell(K_1)$ or the edge $M(K_2)$.

Let $F$ and $H$ be graphs. Let an $F$-forest $T$ be the forest construction used in the source, and let $T^{\star}$ denote its associated graph. Forest sufficient-condition conject…

Let $G$ and $H$ be graphs, let $\Omega_{2d+1}(G)$ denote the graph functor used in the source, and let $n$ be a positive integer. Wrochna's graph-index conjecture. If … then for so…