论文部分内容阅读
Linial and Wilf asked for the graphs with fixed numbers of vertices and edges which maximize the number of proper q-colorings.We characterize the asymptotic structure of extremal graphs for fixed edge density and q.We also disprove a conjecture of Lazebnik,stating that the Turán graph Ts(n)has more q-colorings in its family,by providing counterexamples for s < q < O(s2/log s).When q > 100s2/log s,we show Turán graph indeed achieves the maximum.