𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Sum Multicoloring of Graphs

✍ Scribed by Amotz Bar-Noy; Magnús M. Halldórsson; Guy Kortsarz; Ravit Salman; Hadas Shachnai

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
176 KB
Volume
37
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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 vertex, find a multicoloring which minimizes the sum of the largest colors assigned to the 1

📜 SIMILAR VOLUMES

Graphs omitting sums of complete graphs
Graphs omitting sums of complete graphs
✍ Cherlin, Gregory; Shi, Niandong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 2 views

For every finite m and n there is a finite set {G 1 , . . . , G l } of countable (m • K n )-free graphs such that every countable (m • K n )-free graph occurs as an induced subgraph of one of the graphs G i .

Multicolored trees in complete graphs
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
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.

List multicolorings of graphs with measu
List multicolorings of graphs with measurable sets
✍ A. J. W. Hilton; P. D. Johnson Jr. 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB

## Abstract In an ordinary list multicoloring of a graph, the vertices are “colored” with subsets of pre‐assigned finite sets (called “lists”) in such a way that adjacent vertices are colored with disjoint sets. Here we consider the analog of such colorings in which the lists are measurable sets fr

Highly connected monochromatic subgraphs
Highly connected monochromatic subgraphs of multicolored graphs
✍ Henry Liu; Robert Morris; Noah Prince 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 786 KB

## Abstract We consider the following question of Bollobás: given an __r__‐coloring of __E__(__K~n~__), how large a __k__‐connected subgraph can we find using at most __s__ colors? We provide a partial solution to this problem when __s__=1 (and __n__ is not too small), showing that when __r__=2 the