The Dichromate and Orientations of a Graph
| Autor: | Gerald Berman |
|---|---|
| Rok vydání: | 1977 |
| Předmět: |
Combinatorics
General Mathematics 010102 general mathematics 0103 physical sciences ComputingMethodologies_DOCUMENTANDTEXTPROCESSING Graph (abstract data type) Digraph 010307 mathematical physics 0101 mathematics Chromatic polynomial GeneralLiterature_REFERENCE(e.g. dictionaries encyclopedias glossaries) 01 natural sciences Mathematics |
| Zdroj: | Canadian Journal of Mathematics. 29:947-956 |
| ISSN: | 1496-4279 0008-414X |
| DOI: | 10.4153/cjm-1977-095-1 |
| Popis: | Internal and external activities are defined for any orientation of a graph relative to a fixed labelling of its edges. It is shown that the number of such orientations of having internal activity r and external activity s is 2r+sXrs where Xrs is the coefficient of xrys in the dichromate It follows that the number of orientations of in which the resulting digraph is acyclic is given by , where is the chromatic polynomial associated with . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|