✦ LIBER ✦

Multicoloring trees

✍ Scribed by Magnús M. Halldórsson; Guy Kortsarz; Andrzej Proskurowski; Ravit Salman; Hadas Shachnai; Jan Arne Telle

Book ID: 114273321
Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 195 KB
Volume: 180
Category: Article
ISSN: 0890-5401
DOI: 10.1016/s0890-5401(02)00032-9

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Edge list multicoloring trees: An extens

Edge list multicoloring trees: An extension of Hall's theorem

✍ Mathew Cropper; András Gyárfás; Jenő Lehel 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB

## Abstract We prove a necessary and sufficient condition for the existence of edge list multicoloring of trees. The result extends the Halmos–Vaughan generalization of Hall's theorem on the existence of distinct representatives of sets. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 246–255, 20

Multicolored trees in complete graphs

✍ S. Akbari; A. Alipour 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB

## Abstract A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph __K__~2__n__~(__n__ > 2) with 2__n__ − 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize thi

Multicolored Trees in Complete Graphs

✍ Richard A. Brualdi; Susan Hollingsworth 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 180 KB

We prove the existence of two edge-disjoint multicolored spanning trees in any edge-coloring of a complete graph by perfect matchings; we conjecture that a full partition into multicolored spanning trees is always possible.

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

Routing and path multicoloring

✍ Christos Nomikos; Aris Pagourtzis; Stathis Zachos 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 92 KB

In optical networks it is important to make an optimal use of the available bandwidth. Given a set of requests the goal is to satisfy them by using a minimum number of wavelengths. We introduce a variation to this well known problem, by allowing multiple parallel links, in order to be able to satisf

Sum Multicoloring of Graphs

✍ Amotz Bar-Noy; Magnús M. Halldórsson; Guy Kortsarz; Ravit Salman; Hadas Shachnai 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 176 KB

Scheduling dependent jobs on multiple machines is modeled by the graph multicoloring problem. In this paper we consider the problem of minimizing the average completion time of all jobs. This is formalized as the sum multicoloring problem: Given a graph and the number of colors required by each vert