𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Search and sweep numbers of finite directed acyclic graphs

✍ Scribed by Richard J. Nowakowski

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
719 KB
Volume
41
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

The incremental maintenance of a Depth-F
The incremental maintenance of a Depth-First-Search tree in directed acyclic graphs
✍ Paolo G. Franciosa; Giorgio Gambosi; Umberto Nanni πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 748 KB

We propose an incremental algorithm to maintain a DFS-forest in a directed acyclic graph under a sequence of arc insertions in 0( nm) worst case total time, where n is the number of nodes and m is the number of arcs after the insertions. This compares favorably with the time required to recompute DF

Acyclic graph coloring and the complexit
Acyclic graph coloring and the complexity of the star chromatic number
✍ David R. Guichard πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 294 KB

## Abstract Star chromatic number, introduced by A. Vince, is a natural generalization of chromatic number. We consider the question, β€œWhen is Ο‡\* < Ο‡?” We show that Ο‡\* < Ο‡ if and only if a particular digraph is acyclic and that the decisioin problem associated with this question is probably not i

Chromatic number of finite and infinite
Chromatic number of finite and infinite graphs and hypergraphs
✍ Paul ErdΓΆs; Andras Hajnal πŸ“‚ Article πŸ“… 1985 πŸ› Elsevier Science 🌐 English βš– 349 KB

We wrote many papers on these subjects, some in collaboration with Galvin, Rado, Shelah and Szemer6di, and posed many problems some of which turned out to be undecidable. In this survey we state some old and new solved and unsolved problems. Nous avons 6crit beaucoup d'articles, certains en collabo