Graph colorings and acyclic orientations |
| |
| Authors: | Kiem-Phong Vo |
| |
| Affiliation: | a AT&T Bell Laboratories, Murray Hill, New Jersey, NJ |
| |
| Abstract: | This paper presents new combinatorial proofs of two identities due to R. Stanley relating the chromatic polynomial and acyclic orientations of a graph. In addition, using elementary means, explicit formulae for the generating functions of the chromatic numbers and the number of color compatible acyclic orientations are derived. These formulae immediately show a reciprocity law concerning the generating functions. |
| |
| Keywords: | |
| 本文献已被 InformaWorld 等数据库收录！ |
|
