✦ LIBER ✦

Generating the Acyclic Orientations of a Graph

✍ Scribed by Matthew B Squire

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 206 KB
Volume: 26
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1997.0891

No coin nor oath required. For personal study only.

✦ Synopsis

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 generated. This is the most efficient algorithm known for generating acyclic orientations.

📜 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

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

Generalized Pigeonhole Properties of Gra

Generalized Pigeonhole Properties of Graphs and Oriented Graphs

✍ Anthony Bonato; Peter J Cameron; Dejan Delić; Stéphan Thomassé 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 152 KB

A relational structure A satisfies the P(n, k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of some k of the parts is isomorphic to A. The P(2, 1) property is just the pigeonhole property, (P), introduced by Cameron, and studied

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

On the acyclic choosability of graphs

✍ Mickaël Montassier; Pascal Ochem; André Raspaud 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 348 KB

## Abstract A proper vertex coloring of a graph __G__ = (__V,E__) is acyclic if __G__ contains no bicolored cycle. A graph __G__ is __L__‐list colorable if for a given list assignment __L__ = {L(__v__): __v__ ∈ __V__}, there exists a proper coloring __c__ of __G__ such that __c__ (__v__) ∈ __L__(_