Abstract | ||
---|---|---|
Let F-n,F-tr(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 Turan'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 is an element of F-n,F-tr(n)}. We prove that for all n >= r >= 2, f(n, t(r)(n), r+1) = P-Tr(n)(r+1) and that T-r(n) is the only extremal graph. |
Year | Venue | Field |
---|---|---|
2010 | ELECTRONIC JOURNAL OF COMBINATORICS | Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Partition (number theory),Mathematics,Lambda |
DocType | Volume | Issue |
Journal | 17 | 1.0 |
ISSN | Citations | PageRank |
1077-8926 | 2 | 0.42 |
References | Authors | |
5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Felix Lazebnik | 1 | 353 | 49.26 |
Spencer Tofts | 2 | 5 | 0.84 |