11 problems

Let $G$ be a graph, let $\chi(G)$ denote its chromatic number, and let $K_{\chi(G)}$ be the complete graph on $\chi(G)$ vertices. A weak immersion of a graph $H$ in $G$ consists of…

Füredi–Gyárfás–Simonyi conjecture.

Let $G$ be a graph with a coloring $\mathfrak{C}$ of order $k$, meaning a partition of $V(G)$ into $k$ anticliques, and let $T$ be a transversal of $\mathfrak{C}$. Assume that the…

Let $G$ be a finite simple graph, let $\alpha(G)$ denote its independence number, and let $\operatorname{had}(G)$ denote its Hadwiger number. Seymour's improvement conjecture. Ther…

Independence-number weakening of Hadwiger's conjecture. For any graph $G$,

Weak Hadwiger conjecture. Every graph $G$ with $\alpha(G)\leq 2$ contains

Let $K_t$ denote the complete graph on $t$ vertices. A quasi-$K_t$-minor in a graph $G$ consists of $t$ nonempty, pairwise disjoint vertex sets $B_1,\ldots,B_t$ such that each unio…

Let $G$ be a graph, let $\chi(G)$ denote its chromatic number, and let $t$ be a positive integer. An immersion of a graph $H$ in $G$ is given by an injective map from $V(H)$ to…

Let $k\ge 4$ and let $G$ be a $K_k$-minor-free graph of maximum degree $\Delta$. Strong chromatic index conjecture. The strong chromatic index of $G$ satisfies … This bound is moti…

Let $G$ be a graph, let $\chi(G)$ denote its chromatic number, and let $t$ be a positive integer. An immersion of $G$ is a graph obtained from $G$ by removing vertices or edges and…

Let $D$ be a graphic degree sequence, and let $\mathcal{R}(D)$ be the set of its simple graph realizations. Define $\chi(D)$ as the maximum chromatic number over graphs in…