✦ LIBER ✦

Sinks in Acyclic Orientations of Graphs

✍ Scribed by David D. Gebhard; Bruce E. Sagan

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 183 KB
Volume: 80
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.1975

No coin nor oath required. For personal study only.

✦ Synopsis

Greene and Zaslavsky proved that the number of acyclic orientations of a graph G with a unique sink at a given vertex is, up to sign, the linear coefficient of the chromatic polynomial. We give three proofs of this result using pure induction, noncommutative symmetric functions, and an algorithmic bijection. We also prove their result that if e=u 0 v 0 is an edge of G then the number of acyclic orientations having a unique source at u 0 and unique sink at v 0 is Crapo's beta invariant.

📜 SIMILAR VOLUMES

Acyclic Orientations of Random Graphs

✍ C.M Reidys 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 195 KB

An acyclic orientation of an undirected graph is an orientation of its edges such that the resulting directed graph contains no cycles. The random graph G is a n, p probability space consisting of subgraphs of K that are obtained by selecting each n K -edge with independent probability p. The random

Acyclic and oriented chromatic numbers o

Acyclic and oriented chromatic numbers of graphs

✍ Kostochka, A. V.; Sopena, E.; Zhu, X. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 2 views

The oriented chromatic number χ o ( G) of an oriented graph G = (V, A) is the minimum number of vertices in an oriented graph H for which there exists a homomorphism of G to H. The oriented chromatic number χ o (G) of an undirected graph G is the maximum of the oriented chromatic numbers of all the

Generating the Acyclic Orientations of a

Generating the Acyclic Orientations of a Graph

✍ Matthew B Squire 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 206 KB

The acyclic orientations of a graph are related to its chromatic polynomial, to its reliability, and to certain hyperplane arrangements. In this paper, an algorithm for listing the acyclic orientations of a graph is presented. The algorithm is shown to Ž . require O n time per acyclic orientation ge

On unavoidable digraphs in orientations

On unavoidable digraphs in orientations of graphs

✍ Gary S. Bloom; Stefan A. Burr 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 480 KB

Two-connected orientations of Eulerian g

Two-connected orientations of Eulerian graphs

✍ Alex R. Berg; Tibor Jordán 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB

## Abstract A graph __G__ = (__V__, __E__) is said to be weakly four‐connected if __G__ is 4‐edge‐connected and __G__ – __x__ is 2‐edge‐connected for every __x__ ∈ __V__. We prove that every weakly four‐connected Eulerian graph has a 2‐connected Eulerian orientation. This verifies a special case of

Acyclic edge colorings of graphs

✍ Noga Alon; Benny Sudakov; Ayal Zaks 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract A proper coloring of the edges of a graph __G__ is called __acyclic__ if there is no 2‐colored cycle in __G__. The __acyclic edge chromatic number__ of __G__, denoted by __a′__(__G__), is the least number of colors in an acyclic edge coloring of __G__. For certain graphs __G__, __a′__(_