Maximum number of colorings of (2k, k(2))-Graphs
| Author(s): | Felix Lazebnik, Oleg Pikhurko, Andrew Woldar |
|---|---|
| Year of Publication: | 2007 |
| Journal Title: | Journal of Graph Theory |
| ISSN: | 0364-9024 |
| Volume: | 56 |
| Issue: | 2 |
| Date Name: | Oct 2007 |
| Start Page: | 135 |
| End Page: | 148 |
| Abstract: | Let F-2k,F-k (2) consist of all simple graphs on 2k vertices and k(2) edges. For a simple graph G and a positive integer., let PG(.) denote the number of proper vertex colorings of G in at most lambda colors, and let f(2k, k(2), lambda) = max(P-G(lambda): G is an element of F-2k,k(2)}. We prove that f(2k, k(2), 3) = P-Kk,P-k (3) and K-k,K-k is the only extremal graph. We also prove that f(2k, k(2), 4) = (6 + o(l))4(K) as k -> infinity. (C) 2007 Wiley Periodicals, Inc. |
