The list chromatic number $\chi_L(G)$ is defined to be the minimal $k$ such that for any assignment of a list of $k$ colours to each vertex of $G$ (perhaps different lists for different vertices) a colouring of each vertex by a colour on its list can be chosen such that adjacent vertices receive distinct colours.

The list chromatic number $\chi_L(G)$ is defined to be the minimal $k$ such that for any assignment of a list of $k$ colours to each vertex of $G$ (perhaps different lists for different vertices) a colouring of each vertex by a colour on its list can be chosen such that adjacent vertices receive distinct colours.

Does there exist some constant $c>0$ such that $$\chi_L(G)+\chi_L(G^c)> n^{1/2+c}$$ for every graph $G$ on $n$ vertices (where $G^c$ is the complement of $G$)?

A problem of Erdős, Rubin, and Taylor.

The answer is no: Alon [Al92] proved that, for every $n$, there exists a graph $G$ on $n$ vertices such that $$\chi_L(G)+\chi_L(G^c)\ll (n\log n)^{1/2},$$ where the implied constant is absolute.