SOLVED

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$)?

#753: [ERT80]

graph theory, chromatic number