An extremal property of Turán graphs

Felix Lazebnik ; Spencer Tofts

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

Let ${\cal F}_{n,t_r(n)}$ denote the family of all graphs on $n$ vertices and $t_r(n)$ edges, where $t_r(n)$ is the number of edges in the Turán's graph $T_r(n)$ – the complete $r$-partite graph on $n$ vertices with partition sizes as equal as possible. For a graph $G$ and a positive integer $\lambda$, let $P_G(\lambda)$ denote the number of proper vertex colorings of $G$ with at most $\lambda$ colors, and let $f(n,t_r(n),\lambda) = \max\{P_G(\lambda):G \in {\cal F}_{n,t_r(n)}\}$. We prove that for all $n\ge r\ge 2$, $f(n,t_r(n),r+1) = P_{T_r(n)}(r+1)$ and that $T_r(n)$ is the only extremal graph.

Détail

DOI : 10.37236/442

Classification : 05C15, 05C30, 05C31, 05C35
Mots-clés : Turan graph, proper vertex coloring