21 problems

Let $G$ be a multipartite graph with parts $V_i$, and let $\Delta(G)$ denote its maximum degree. An independent transversal is an independent set containing exactly one vertex from…

Independent transversal decomposition conjecture. If

Disjoint-independent-transversal conjecture. If $m\ge2n-1$, then $A$ has $m-(n-1)$ pairwise disjoint ITs.

Let $G$ be a graph, let $\mathcal{U} = \{U_1, \ldots, U_m\}$ be a partition of $V(G)$, and let $k \ge -1$. Write $\mathbf{Col}(\mathcal{I}(G),\mathcal{U})$ for the colorful complex…

Let $\mathcal{G}_r(n)$ be the class of $r$-partite graphs with parts of size $n$. An independent transversal with exactly $s$ vertices in each part is denoted by $IT(s)$. Odd-parti…

Let $\mathcal{G}_r(n)$ be the class of $r$-partite graphs whose parts all have size $n$. Let $\Delta_r(n)$ be the largest integer $C$ such that every graph in $\mathcal{G}_r(n)$ wi…

Let $G$ be a graph with maximum degree $\Delta$ and let $\mathcal{U}$ be a $(2\Delta)$-thick partition of $V(G)$. An independent transversal is a set containing exactly one vertex…

Let $G$ be a multipartite graph with parts $V_1,\ldots,V_k$ of the same size $n$, maximum degree at most $(1-\varepsilon)n$ for some $\varepsilon>0$, and at most $o(n)$ neighbors i…

Let $G$ be a $K_{1,k}$-free graph with maximum degree $d$, and let … be a partition of $V(G)$. An independent transversal (IT) is an independent set containing exactly one vertex f…

Let $G$ and $H$ be bipartite graphs, with bipartitions $V(G)=A_G\cup B_G$ and $V(H)=A_H\cup B_H$. Let $H$ be a bipartite list-cover of $G$ with respect to a mapping $L$, meaning th…

Independent-transversal packing conjecture.

Strong colouring conjecture.

Let $G$ be a graph and let $\mathcal P$ be a $t$-thick vertex partition of $G$, meaning that every block of $\mathcal P$ has size at least $t$. Write $|\mathcal P|$ for the number…

The conjecture on $f(k,s)$. It is conjectured that

The conjecture on $f(k)$. For every $k\ge 2$,

For integers $n,k,r,s$, let $f(k,r,s)$ be the extremal function for independent transversals in $(n,k,r,s)$-graphs. Fix $r\ge 3$. Yuster's conjecture. For all $1\le s\le k$, … The…

For positive integers $n,k,r,s$, let $f(k,r,s)$ denote the largest $n$ such that every $(n,k,r,s)$-graph has an independent transversal. In the case $r=2$, Yuster's conjecture. For…

Let $G$ be a graph whose vertex set is partitioned into parts, and suppose that every two parts induce a matching. An independent transversal is an independent set containing exact…

Let $G$ be a non-complete connected graph on $n$ vertices. For a graph $G$, an independent transversal dominating set is a dominating set $S\subseteq V(G)$ such that…

Let $H$ be a simple bipartite graph, let $L(H)$ be its line graph, and let $V_1,\ldots,V_m$ be a partition of the edge set of $L(H)$. An independent system of representatives (ISR)…

Aharoni–Holzman conjecture. Their distance condition can be replaced by the weaker condition that the local degree is $1$, while still guaranteeing an independent transversal.