Erdős Problem #753

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.