Abstract | ||
---|---|---|
Let ℱ2k, k2 consist of allsimple graphs on 2k vertices and k2edges. For a simple graph G and a positive integerλ, let PG(λ) denotethe number of proper vertex colorings of G in at mostλ colors, and let f(2k, k2,λ) =max{PG(λ):Gεℱ2k,k2}.We prove that f(2k, k2, 3) =PKk,k(3) and Kk,k is theonly extremal graph. We also prove that f(2k,k2, 4) = (6+o(1))4k ask ➝ ∞. © 2007 Wiley Periodicals,Inc. J Graph Theory 56: 135148, 2007 |
Year | DOI | Venue |
---|---|---|
2007 | 10.1002/jgt.v56:2 | Journal of Graph Theory |
Keywords | DocType | Volume |
allsimple graph,simple graph,theonly extremal graph,Inc. J Graph Theory,Wiley Periodicals,denotethe number,positive integer,proper vertex colorings,maximum number | Journal | 56 |
Issue | Citations | PageRank |
2 | 2 | 0.47 |
References | Authors | |
1 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Felix Lazebnik | 1 | 353 | 49.26 |
Oleg Pikhurko | 2 | 318 | 47.03 |
Andrew J. Woldar | 3 | 88 | 11.20 |