𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generalized Parking Functions, Tree Inversions, and Multicolored Graphs

✍ Scribed by Catherine H. Yan

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
272 KB
Volume
27
Category
Article
ISSN
0196-8858

No coin nor oath required. For personal study only.

✦ Synopsis

A generalized x-parking function associated to a positive integer vector of the form a b b b is a sequence a 1 a 2 a n of positive integers whose

The set of x-parking functions has the same cardinality as the set of sequences of rooted b-forests on n . We construct a bijection between these two sets. We show that the sum enumerator of complements of x-parking functions is identical to the inversion enumerator of sequences of rooted b-forests by generating function analysis. Combinatorial correspondences between the sequences of rooted forests and x-parking functions are also given in terms of depth-first search and breadth-first search on multicolored graphs.

πŸ“œ SIMILAR VOLUMES

Generalized Tree Inversions andk-Parking
Generalized Tree Inversions andk-Parking Functions
✍ Catherine Huafei Yan πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 298 KB

Kreweras studied a polynomial P n (q) which enumerates (labeled) rooted forests by number of inversions, as well as complements of parking functions by the sum of their terms. Moreover, P n (1+q) enumerates labeled connected graphs by their number of excess edges. For any positive integer k, there a

Tools for Multicoloring with Application
Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
✍ MagnΓΊs M. HalldΓ³rsson; Guy Kortsarz πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 240 KB

We study graph multicoloring problems, motivated by the scheduling of dependent jobs on multiple machines. In multicoloring problems, vertices have lengths which determine the number of colors they must receive, and the desired coloring can be either contiguous (nonpreemptive schedule) or arbitrary