59 problems

Kneser's conjecture. The chromatic number of $\operatorname{Kn}(q,k)$ is

Meunier's conjecture. For all $s\geq 2$ and $n\geq sk$,

For positive integers $n$ and $k$ with $n\geq 2k$, let $\operatorname{KG}(n,k)$ be the Kneser graph and let $\chi_c(G)$ denote the circular chromatic number of a graph $G$. Johnson…

Stahl's conjecture. For all $q\ge1$ and $0\le r\le k-1$, one has

Let $K(n,k)$ be the Kneser graph whose vertices are the $k$-subsets of $[n]$, with two vertices adjacent when the corresponding sets are disjoint. For an integer $s\geq 3$, a famil…

Kneser graph Hamiltonicity conjecture. Kneser graphs are Hamiltonian, except for the Petersen graph $KG_{5,2}$.

Let $r,q\in\mathbb{N}$, and partition the $r$-subsets of a $(2r+q-1)$-element set into $q$ classes. Kneser's conjecture. One of the classes contains two disjoint $r$-subsets. This…

Let $n\geq 5$, and let $\operatorname{K}(n,2)$ be the Kneser graph whose vertices are the $2$-element subsets of $[n]$, with two vertices adjacent when the corresponding subsets ar…

Let $K(m,n)$ be the Kneser graph whose vertices are the $n$-subsets of $\{1,\ldots,m\}$, with two vertices adjacent when the corresponding subsets are disjoint. For an integer $r$,…

For $k\geq 1$, let $O_k:=K(2k+1,k)$ be the odd graph, where $K(n,k)$ is the graph whose vertices are the $k$-element subsets of $[n]:=\\{1,\ldots,n\\}$ and whose edges join disjoin…

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…

Kalai–Meagher conjecture. For every $n\geq 3$,

Let $f_\ell(n,k)$ denote the clique number of the xor-product of $\ell$ copies of the Kneser graph $KG(n,k)$. Fix $\ell$ and suppose that $k$ is sufficiently large. Higher-power gr…

Let $n,k$ be positive integers with $k\geq2$, and let $\vec{s}=(s_1,\ldots,s_k)$ be a positive integer vector with $s_i\geq2$ for $1\leq i\leq k-1$. Let…

Kneser graph Class 0 conjecture. Every Kneser graph is Class $0$.

Chen–Raspaud conjecture. For each integer $k\ge 2$, any graph $G$ satisfying

Exact homology-rank conjecture. The rank of the $p$-dimensional homology group of $\operatorname{Ind}(\operatorname{KG}(n,k))$ is

Erdős matching conjecture. If $n\geq k(s+1)$ and $\mathcal{F}\subseteq\binom{[n]}{k}$ satisfies

Dense minimizer conjecture. There exists a family

Sparse minimizer conjecture. There exists a minimizer $\mathcal{F}$ such that

For integers $k\geq 1$ and $n\geq 2k+1$, let $K_{n,k}$ be the Kneser graph whose vertices are the $k$-element subsets of $[n]$, with edges joining disjoint sets. For a graph, the…

For $k\geq 3$, let $O_k:=K_{2k+1,k}$ be the odd graph. A collection of Hamilton cycles is edge-disjoint if no edge belongs to more than one cycle. Biggs's conjecture. The odd graph…

For integers $k\geq 1$ and $n\geq 2k+1$, let $H_{n,k}$ be the bipartite Kneser graph whose vertices are the $k$-element and $(n-k)$-element subsets of $[n]$, with an edge between…

Let $K(n,r)$ be the Kneser graph whose vertices are the $r$-subsets of $[n]$, with two vertices adjacent when they are disjoint. A subset $C$ of the vertices of a graph is a perfec…

Let $q$ be a prime power with $q\equiv 3\pmod{4}$, and consider the Kneser graph $K(q+1,3)$ and its automorphism group. Maximum-density conjecture. The group…