Premium
Estimates of coefficients of chromatic polynomials and numbers of cliques of ( c,n,m )‐graphs
Author(s) -
Pitteloud Philippe
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10039
Subject(s) - combinatorics , mathematics , chromatic scale , upper and lower bounds , graph , discrete mathematics , windmill graph , chromatic polynomial , graph power , line graph , mathematical analysis
This paper is mainly concerned with classes of simple graphs with exactly c connected components, n vertices and m edges, for fixed c,n,m ∈ ℕ. We find an optimal lower bound for the i th coefficient of the chromatic polynomial of a graph in such a class and also an optimal upper bound for the number of j ‐cliques contained in such a graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 81–94, 2003