JOURNAL OF COMBINATORIALTHEORY 4, 52-71 (1968) An Introduction to Chromatic Polynomials* RONALD C. READ Department of Mathematics, University of the West Indies, Kingston, Jamaica Communicated by Frank Harary ABSTRACT This expository paper is a general introduction to the theory of chromatic pol- ynomials. Chromatic polynomials are defined, their salient properties are derived, and some practicaI methods for computing them are given. A brief mention is made of the connection between the theory of chromatic polynomials and map coloring problems. The paper concludes with some unsolved problems relating to chromatic polynomials and to applications of the theory to practical problems in operations research. 1. INTRODUCTION There are many interesting problems which arise when one considers the ways of coloring the nodes of a graph subject to certain restrictions. The object of this paper is to give a brief account of the fundamentals of this branch of graph theory. A coloring of a graph is the result of giving to each node of the graph one of a specified set of colors. In more mathematical terms it is a mapping of the nodes into (or onto) a specified finite set C (the set of colors). We shall leave for the moment the question of whether the mapping is to be into or onto. By a proper coloring of a graph will be meant a coloring which satisfies the restriction that adjacent nodes are not given (., mapped onto) the same color (element) of C. A coloring for which this is not true will be called an improper coloring. These are the definitions; but it so happens that we shall nearly always be concerned with proper colorings only, and it will therefore be con- venient to drop the term "proper" and agree that by "colorings" of a graph we mean "proper colorings" unless the c
an introduction to chromatic polynomials英文 来自beplayapp体育下载www.apt-nc.com转载请标明出处.