✦ LIBER ✦

Searching for acyclic orientations of graphs

✍ Scribed by Martin Aigner; Eberhard Triesch; Zsolt Tuza

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 397 KB
Volume: 144
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00281-m

No coin nor oath required. For personal study only.

✦ Synopsis

We want to find an unknown acyclic orientation ~* of an (undirected) graph G by testing for certain edges how they are oriented according to ~*. How many tests do we need in the worst case? We give upper and lower bounds for this number c(G) in terms of the independence number of G and study the class of exhaustive graphs, i.e~ graphs satisfying c(G) --]E(G)]. It is shown that there exist nonexhaustive graphs with arbitrarily large girth. The extremal exhaustive graphs are determined for n/> 7.

📜 SIMILAR VOLUMES

Acyclic orientations of graphs

✍ Richard P. Stanley 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 708 KB

## Let G be a finite graph with p vertices and x its chromatic polynomial. A combinatorial interpretation is given to the positive integer (-l)px(-A), where h is a positive integer, in terms of acyclic orientations of G. In particular, (-l)Px(-1) is the number of acyclic orientations of G. An appl

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 orientations of complete biparti

Acyclic orientations of complete bipartite graphs

✍ Douglas B. West 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 216 KB

For a complete bipartite graph, the number of dependent edges in an acyclic orientation can be any integer from n-1 to e, where n and e are the number of vertices and edges in the graph. ## Ke3,words: Bipartite graph; Acyclic orientation Ill combinatorics we often ask whether an integer parameter

Transversals of circuits and acyclic ori

Transversals of circuits and acyclic orientations in graphs and matroids

✍ C. Berge; M. Las Vergnas 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 132 KB

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