15 problems

Maximum independent edge set conjecture.

Let $G$ be a graph, let $F_k(G)$ denote its $k$-token graph, and let a $k$-token reconstruction family of $F_k(G)$ be a family of subsets as defined in the source. Let…

Let $G=(V,E)$ be a graph, let $F_k(G)$ be its $k$-th token graph, and define … Let $\nu(G)$ denote the matching number of $G$. Apte–Parekh–Sud's token-excess conjecture. For…

Let $G=(V,E)$ be a graph and let $F_k(G)$ be its $k$-th token graph, whose vertices are the $k$-element subsets of $V$. For $1\le k\le |V|/2$, let $L(F_k(G))$ denote the Laplacian…

Covering conjecture for 2-token star graphs. The token graph $F_2(K_{1,n})$ is isomorphic to a covering graph $X^{(\alpha,\omega)}$ of a base graph $X$ on $n-k$ vertices, with comb…

Covering conjecture for odd-star token graphs. The token graph $F_k(K_{1,n})$ is isomorphic to a covering graph $X^{(\alpha,\omega)}$ of a base graph $X$ on

Let $G$) be a tree on $n$ vertices, and let $F_k(G)$ denote its $k$-token graph, whose vertices are the $k$-subsets of $V(G)$. For a fixed integer $k$ satisfying $1\le k\le n-1$, t…

Let $G$ be a graph on $n$ vertices. For each $k$ with $1\le k\le \lfloor n/2\rfloor$, let $\rho_k(G)$ denote the spectral radius of its $k$-token graph. Monotonicity conjecture. Fo…

Let $G$ be a graph on $n$ vertices. For each $k$ with $1\le k\le \lfloor n/2\rfloor$, let $\alpha_k(G)$ denote the algebraic connectivity of its $k$-token graph. Monotonicity conje…

Dalfó et al.'s conjecture. For any graph $G$ on $n$ vertices and any $1\leq k\leq n-1$,

Let $G$) be a connected graph with $n\geq 5$ vertices and prime factor decomposition … where $r>1$. Let $\psi$ be the homomorphism from $\operatorname{Aut}(G)$ to…

Let $S_m$ be the star graph on $m+1$ vertices, and let $\tok{S_m}{n}$ denote its token graph. Write $A_1(-)$ for the first homology group. The graph $\tok{S_m}{n}$ is known to have…

Fabila-Monroy et al.'s connectivity conjecture. If $G$ is $t$-connected and $k\leq t$, then

Token-graph connectivity conjecture. If $G$ is $t$-connected and $k\leq t$, then $F_k(G)$ is at least $k(t-k+1)$-connected.

Let $A085680(n)$ denote the packing number of the double vertex graph of the path graph $P_n$, equivalently $\rho(F_2(P_n))$, where $F_2(P_n)$ is the 2-token graph of $P_n$. Rob Pr…