✦ LIBER ✦

Acyclic Orientations of Random Graphs

✍ Scribed by C.M Reidys

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 195 KB
Volume: 21
Category: Article
ISSN: 0196-8858
DOI: 10.1006/aama.1998.0595

No coin nor oath required. For personal study only.

✦ Synopsis

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 graph Q n is defined n 2, p analogously and consists of subgraphs of the n-cube, Q n . In this paper we first 2 derive a bijection between certain equivalence classes of permutations and acyclic Ž . orientations. Second, we present a lower and an upper bound on the r.v. a G n, p that counts the number of acyclic orientations of G . Finally we study the n, p Ž . Ž n . Ž . Ž n . distribution of a G and a Q and show that log a G and log a Q n, p 2, p 2 n, p 2 2 ,p are sharply concentrated at their respective expectation values.

📜 SIMILAR VOLUMES

Sinks in Acyclic Orientations of Graphs

✍ David D. Gebhard; Bruce E. Sagan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 183 KB

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 b

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

The generalized acyclic edge chromatic n

The generalized acyclic edge chromatic number of random regular graphs

✍ Stefanie Gerke; Catherine Greenhill; Nicholas Wormald 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract The __r__‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle __C__ has at least min(|__C__|, __r__) colors. We show that (__r__ − 2)__d

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

A phase transition phenomenon in a rando

A phase transition phenomenon in a random directed acyclic graph

✍ B. Pittel; R. Tungol 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB

Let a random directed acyclic graph be defined as being obtained from the random graph G n p by orienting the edges according to the ordering of vertices. Let γ \* n be the size of the largest (reflexive, transitive) closure of a vertex. For p = c log n /n, we prove that, with high probability, γ \*