191 problems

Conjecture of Faber, Lovász and myself. Let $G_1, \ldots, G_n$ be $n$ edge-disjoint complete graphs on $n$ vertices. We conjectured more than 20 years ago that the chromatic number…

Let $G$ be a finite graph and let $t\in\mathbb{N}$. A minor of $G$ is a graph obtainable from $G$ by a sequence of vertex deletions, edge deletions, and edge contractions; write…

Let $G$ be a graph, with maximum degree $\Delta(G)$ and clique number $\omega(G)$. Reed's conjecture. Every graph $G$ satisfies … This refines the Borodin–Kostochka direction and i…

Let $G=(V,E)$ and $H=(V',E')$ be graphs. Their categorical product $G\times H$ has vertex set $V\times V'$ and an edge between $(u,u')$ and $(v,v')$ exactly when $uv\in E$ and…

Hajós's conjecture. The graph $G$ contains a subdivision of $K_r$.

All graphs considered are finite, simple, and undirected. For a graph $G$, let $\chi(G)$ denote its chromatic number, $\omega(G)$ its clique number, and $\Delta(G)$ its maximum deg…

Let $T$ be an oriented tree on $n$ vertices. An oriented graph $H$ is $\chi$-universal if every digraph of chromatic number $\chi$ contains $H$ as a subdigraph. Burr's conjecture.…

Let $G_{n,p}$ be the random graph on $n$ vertices, let $G_{n,p}^r$ denote its $r$th power, and write $\chi(G)$ and $\alpha(G)$ for the chromatic and independence numbers of a graph…

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…

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

Let $G$ be a triangle-free graph, let $\chi(G)$ denote its chromatic number, and let $\rho(G)$ denote its spectral radius. Spectral-radius chromatic bound. Every triangle-free grap…

Let $G$ be a graph with independence number $\alpha(G)=2$, let $\chi(G)$ denote its chromatic number, and let $K_{\chi(G)}$ be the complete graph on $\chi(G)$ vertices. A weak imme…

Erdős–Lovász–Tihany Conjecture. If

Let $P$ be an oriented path with two blocks on $n\ge 4$ vertices. An oriented graph $H$ is $\chi$-universal if every digraph of chromatic number $\chi$ contains $H$ as a subdigraph…

Let $k_1,k_2,\dots,k_n$ be positive integers. A subdivision of an oriented cycle $C(k_1,k_2,\dots,k_n)$ is obtained by replacing each arc by a directed path of length at least $1$,…

Wu–Xu–Xu conjecture. Every graph in $\bigcup_{\ell\geq 2}{\cal H}_{\ell}$ is $3$-colorable.

Let $s$ be a positive integer, and let $c_s$ be a constant such that $G$ is a graph with $N$ vertices containing no odd cycles of length less than $c_sN^{1/s}$. Erdős's conjecture.…

Let $G$ be a finite simple graph, and let $\chi(G)$ denote its chromatic number. For positive integers $\ell$ with $\ell<\chi(G)$, let $K_{\ell,\chi(G)-\ell}$ be the complete bipar…

Let $t$ be a positive integer and let $G$ be a graph. A $K_t$ minor is a minor of $G$ isomorphic to the complete graph on $t$ vertices. A graph is $ct$-colourable if its vertices c…

For a graph $G$, let $R_\chi(G)$ be its chromatic Ramsey number, and define … Burr–Erdős–Lovász conjecture. For every positive integer $n$, … The source states this conjecture as a…

El-Zahar–Erdős conjecture. For every pair of integers $t,c\geq 1$, there exists $d\geq 1$ such that if $\chi(G)\geq d$ and $\omega(G)<t$, then there are subsets $A,B\subseteq V(G)$…

Let $G$ be a graph, let $\Delta(G)$ be its maximum degree, and let $\chi(G)$ and $\chi_\ell(G)$ denote its chromatic and list chromatic numbers. Half-maximum-degree conjecture. Eve…

Let $\chi_{\varepsilon}(\mathbb{R}^2)$ denote the least number of colors in a coloring of the plane with no monochromatic pair of points at a distance in…

Let $S^{n-1}$ be the unit sphere in Euclidean $n$-space, and let $A\subset S^{n-1}$ be a measurable set. Call $A$ orthogonality-free if it does not contain two orthogonal vectors.…

Let $S^2_r$ be the 2-dimensional sphere of radius $r>1/2$, and let a three-coloring assign one of three colors to every point of $S^2_r$. Simmons's conjecture. Every such coloring…