Abstract | ||
---|---|---|
Let F denote the family of simple undirected graphs on v vertices having e edges, P ( G ; λ ) be the chromatic polynomial of a graph G . For the given integers v , e , λ , let f ( v , e , λ )= max\s{ P ( G;λ ): G ∈ F \s}. In this paper we determine some lower and upper bounds for f ( v , e , λ ) provided that λ is sufficiently large. In some cases f ( v , e , λ ) is found and all graphs G for which P ( G ; λ ) = f ( v , e , λ ) are described. Connections between these problems and some other questions from the extremal graph theory are analysed using Whitney's characterization of the coefficients of P ( G ; λ ) in terms of the number of ‘broken circuits’ in G . |
Year | DOI | Venue |
---|---|---|
1991 | 10.1016/0012-365X(91)90070-I | Discrete Mathematics |
Keywords | Field | DocType |
chromatic polynomial | Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Chromatic polynomial,Extremal graph theory,Mathematics | Journal |
Volume | Issue | ISSN |
87 | 1 | Discrete Mathematics |
Citations | PageRank | References |
12 | 1.83 | 5 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Felix Lazebnik | 1 | 353 | 49.26 |