论文标题
关于颜色的数量
The extremality of 2-partite Turán graphs with respect to the number of colorings
论文作者
论文摘要
我们考虑了Linial和Wilf提出的一个问题，以确定图形结构，该结构允许具有$ n $顶点和$ M $边缘的图表中最大数量的$ Q $ - 色。令$ t_r（n）$表示Turán图 - $ n $顶点上的完整$ r $ - 分段图，分区尺寸尽可能相等。我们证明，对于所有奇数整数$ q \ geq 5 $和足够大的$ n $，turán图$ t_2（n）$具有与任何其他图形$ g $具有相同数量的顶点和边缘的$ q $ colorings，与$ t_2（n）$相同，仅等于$ g = t_2（n）$。我们的证明是基于Norine和Loh，Pikhurko和Sudakov的方法的基础，这些方法将问题减少到了二次程序。
We consider a problem proposed by Linial and Wilf to determine the structure of graphs that allows the maximum number of $q$-colorings among graphs with $n$ vertices and $m$ edges. Let $T_r(n)$ denote the Turán graph - the complete $r$-partite graph on $n$ vertices with partition sizes as equal as possible. We prove that for all odd integers $q\geq 5$ and sufficiently large $n$, the Turán graph $T_2(n)$ has at least as many $q$-colorings as any other graph $G$ with the same number of vertices and edges as $T_2(n)$, with equality holding if and only if $G=T_2(n)$. Our proof builds on methods by Norine and by Loh, Pikhurko, and Sudakov, which reduces the problem to a quadratic program.
